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

梦里梦外; 2022-12-12 04:52 146阅读 0赞

**从上之下一次找p和q的祖先链条，一直找到root  
分别存在数组里面  
然后找公共的祖先的最小的那个**

#define debug(x) cout<<#x<<": "<<(x)<<endl;
    
    class Solution { 
    public:
        vector<TreeNode*> pf;
        vector<TreeNode*> qf;
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { 
            rootIsFatherOf(qf,root,q);
            rootIsFatherOf(pf,root,p);
            if(pf.size() == 0 || qf.size() == 0){ 
                return root;
            }
            int i = pf.size()-1;
            int j = qf.size()-1;
            TreeNode * ret = nullptr;
            for(;i>=0 && j>=0;){ 
                if(pf[i] == qf[j]){ 
                    ret = pf[i];
                    i--,j--;
                }else{ 
                    break;
                }
            }
            if(ret == nullptr){ 
                return root;
            }
            return ret;
        }
        
        bool rootIsFatherOf(vector<TreeNode*> &ve,TreeNode* root,TreeNode* p){ 
            if(root == nullptr){ 
                return false;
            }
            if(root == p){ 
                return true;
            }
            else if( rootIsFatherOf(ve,root->left,p) ){ 
                ve.push_back(root->left);
                return true;
            }
            else if( rootIsFatherOf(ve,root->right,p) ){ 
                ve.push_back(root->right);
                return true;
            }else{ 
                return false;
            }
            return false;
        }
    };

![在这里插入图片描述][20201006131354313.png_pic_center]

--------------------

**递归**

**答案参考:** [https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/comments/][https_leetcode-cn.com_problems_lowest-common-ancestor-of-a-binary-tree_comments]

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

![在这里插入图片描述][20201006132423422.png_pic_center]

[20201006131354313.png_pic_center]: /images/20221123/eab79a3727b640ed89cffde14d9a35b4.png
[https_leetcode-cn.com_problems_lowest-common-ancestor-of-a-binary-tree_comments]: https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/comments/
[20201006132423422.png_pic_center]: /images/20221123/f0a908b2db934aa1b4959710ea477b7a.png