236. Lowest Common Ancestor of a Binary Tree.md

236. Lowest Common Ancestor of a Binary Tree

思路

给定一棵二叉树和其中的两个节点，求这两个节点的最小公共祖先。

思路一

比较好想的是先分别把p和q的祖先都求出来，再从最高往下比较两者的祖先们即可。

所以此题转换成求根到某个节点的所有祖先。我们可以采取先序遍历的思路进行递归求解，并用一个path数组保存路径。

思路二

也可以直接递归求解，递归出口就是当root为空或这root为p、q任意一个，否则我们在左右子树中分别递归求解得到left_lca和right_lca:

• 若left_lca为空，说明pq都在右子树，那么应该返回right_lca；
• 否则，若right_lca为空，说明pq都在左子树，那么应该返回left_lca；
• 否则，即二者皆为空，说明pq分别在左右子树，那么lca就是root。

上述过程有一个前提：当树中只有p（或q）时，lca等于p（或q）

C++

思路一

class Solution {
private:
    // 若已经访问到target则返回true
    bool root_path(TreeNode* root, TreeNode* target, vector<TreeNode*>& path){
        if(!root) return false;
        path.push_back(root);
        if(root -> val == target -> val) return true;
        if(root_path(root -> left, target, path)) return true;
        if(root_path(root -> right, target, path)) return true;
        path.pop_back();
        return false;
    }
    
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        vector<TreeNode* >p_path;
        vector<TreeNode* >q_path;
        
        root_path(root, p, p_path);
        root_path(root, q, q_path);
        
        int i = 1;
        for(; i < min(p_path.size(), q_path.size()); i++)
            if(p_path[i] != q_path[i]) return p_path[i-1];
        
        return p_path[i-1];   
    }
};

思路二

public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
            // 当树中只有p（或q）时，lca等于p（或q）
            if (!root || root == p || root == q) return root;
            TreeNode* left_lca = lowestCommonAncestor(root->left, p, q);
            TreeNode* right_lca = lowestCommonAncestor(root->right, p, q);
            if(!left_lca) return right_lca; // pq全在右边
            if(!right_lca) return left_lca; // pq全在左边
            return root; // 左右都有       
    }
};