给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
分两种情况讨论最近公共节点如何判断
递归写法
TreeNode* ans; bool dfs(TreeNode* root, TreeNode* p, TreeNode* q){ if(root==nullptr){ return false; } bool lson=dfs(root->left,p,q);//递归 bool rson=dfs(root->right,p,q); if((lson&&rson)||((root==p||root==q)&&(lson||rson))){//记录公共祖先结点 ans=root; } return lson||rson||(root==p||root==q);//子树是否包括p或q } TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { dfs(root,p,q); return ans; }
记录父节点
遍历二叉树将每个结点与父结点的关系存储进map。
从p开始遍历把所有父结点设为true，从q开始同样操作如果遇到true则是最近公共祖先节点。
class Solution { public: unordered_map<int, TreeNode*> fa; unordered_map<int, bool> vis; void dfs(TreeNode* root){//制作父结点散列表 if (root->left != nullptr) { fa[root->left->val] = root; dfs(root->left); } if (root->right != nullptr) { fa[root->right->val] = root; dfs(root->right); } } TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { fa[root->val] = nullptr; dfs(root); while (p != nullptr) {//标记p所有父结点 vis[p->val] = true; p = fa[p->val]; } while (q != nullptr) {//寻找q与p的最近公共祖先结点 if (vis[q->val]) return q; q = fa[q->val]; } return nullptr; } };
