LeetCode刷题笔记-数据结构-day18

蔚落 2023-10-01 17:05 40阅读 0赞

#### 文章目录 ####

*  LeetCode刷题笔记-数据结构-day18
 *   *  236. 二叉树的最近公共祖先
     *   *  1.题目描述
         *  2.解题思路
         *  3.代码
     *  297. 二叉树的序列化与反序列化
     *   *  1.题目描述
         *  2.解题思路
         *  3.代码

## LeetCode刷题笔记-数据结构-day18 ##

### 236. 二叉树的最近公共祖先 ###

#### 1.题目描述 ####

> 原题链接：[236. 二叉树的最近公共祖先][236.]

![image-20220202104534978][]

![image-20220202104547515][]

#### 2.解题思路 ####

算法：`DFS`

`p`和`q`的最近公共祖先可分为这几种情况：

1.  若当前节点root == p，则表示q点一定在root的左右子树其中一处，则最近的公共结点肯定是p
2.  若当前节点root == q，则表示p点一定在root的左右子树其中一处，则最近的公共结点肯定是q
3.  若1和2情况都不是，则p和q的最近公共祖先要么在root的左子树，要么在root的右子树，则直接递归到root->left和root->right进行搜索。若递归完后，左子树返回null表示没找到，那答案肯定是在右子树，同理，右子树返回null表示没找到，那答案肯定是在左子树
4.  若3情况中左右子树都找不到p和q的最近公共祖先，则表示p点和q点分别在不同的左右子树，则root就是他们的最近公共祖先，直接返回root

#### 3.代码 ####

class Solution {
        
        public:
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        
            if(!root) return NULL;
            if(root==p||root==q) return root;
            TreeNode* left=lowestCommonAncestor(root->left,p,q);
            TreeNode* right=lowestCommonAncestor(root->right,p,q);
            if(!left) return right;
            if(!right) return left;
            return root;
        }
    };

### 297. 二叉树的序列化与反序列化 ###

#### 1.题目描述 ####

> 原题链接：[297. 二叉树的序列化与反序列化][297.]

![image-20220202104618337][]

![image-20220202104656775][]

#### 2.解题思路 ####

算法：`DFS`

1.  序列化：把整个二叉树进行先序遍历的序列存起来，同时需要把每个结点的空节点使用 `#` 进行标记
2.  反序列化：反序列化时，按照 `,` 作为分隔，构造当前结点后分别通过递归构造左右子树

> 建议参考官方题解：[官方题解][Link 1]

#### 3.代码 ####

class Codec {
        
    public:
        string path;
        // Encodes a tree to a single string.
        string serialize(TreeNode* root) {
        
            dfsD(root);
            return path;
        }
        void dfsD(TreeNode* root){
        
            if(!root){
        
                path+="#,";
            }else{
        
                path+=to_string(root->val)+",";
                dfsD(root->left);
                dfsD(root->right);
            }
        }
    
        // Decodes your encoded data to tree.
        TreeNode* deserialize(string data) {
        
            int u=0;
            return dfsS(data,u);
    
        }
        TreeNode* dfsS(string& data,int& u){
        
            if(data[u]=='#'){
        
                u+=2;
                return NULL;
            }
            int k=u;
            while(data[u]!=',') u++;
            TreeNode* t=new TreeNode(stoi(data.substr(k,u-k)));
            u++;
            t->left=dfsS(data,u);
            t->right=dfsS(data,u);
            return t;
        }
    };

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBATEwuTEVCUk9O_size_20_color_FFFFFF_t_70_g_se_x_16]

[236.]: https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/
[image-20220202104534978]: https://img-blog.csdnimg.cn/img_convert/d12f43f38736afcfe0703f16dea69cfa.png
[image-20220202104547515]: https://img-blog.csdnimg.cn/img_convert/8ef246f97e1863d2a755f47f77f6fce8.png
[297.]: https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/
[image-20220202104618337]: https://img-blog.csdnimg.cn/img_convert/43e7b4687d722c67f91af4584acfea7a.png
[image-20220202104656775]: https://img-blog.csdnimg.cn/img_convert/885ac9ad7a0a9d04356486cf73995311.png
[Link 1]: https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/solution/er-cha-shu-de-xu-lie-hua-yu-fan-xu-lie-hua-by-le-2/
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBATEwuTEVCUk9O_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/f132713a0b264824ba4d82163f619970.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBATEwuTEVCUk9O,size_20,color_FFFFFF,t_70,g_se,x_16