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

文章目录

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

236、二叉树的最近公共祖先

1.题目描述2.解题思路3.代码 297、二叉树的序列化与反序列化

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

原题链接：236、二叉树的最近公共祖先

2.解题思路

算法：DFS

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

若当前节点root == p，则表示q点一定在root的左右子树其中一处，则最近的公共结点肯定是p若当前节点root == q，则表示p点一定在root的左右子树其中一处，则最近的公共结点肯定是q若1和2情况都不是，则p和q的最近公共祖先要么在root的左子树，要么在root的右子树，则直接递归到root->left和root->right进行搜索。若递归完后，左子树返回null表示没找到，那答案肯定是在右子树，同理，右子树返回null表示没找到，那答案肯定是在左子树若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、二叉树的序列化与反序列化

2.解题思路

算法：DFS

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

建议参考官方题解：官方题解

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; }};