Lowest Common Ancestor

Sep 08, 2020
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    	// 找到叶子都没有,返回null
        if (!root) return nullptr;
        // 如果找到了就返回这个节点
        if (root == p || root == q) return root;
		
        // 后续遍历
        auto left = lowestCommonAncestor(root->left, p, q);
        auto right = lowestCommonAncestor(root->right, p, q);
        
        // 后续遍历可以节点可以获取子节点的信息
        // 如果p q都存在与两个子树中
        if (left && right)
            return root;
        
        // 往上返回 表明来自哪一个子树
        if (left) return left;
        if (right) return right;
        
        // 如果p q都不在子树中,返回null
        return nullptr;
    }
};
Great! You've successfully subscribed.
Great! Next, complete checkout for full access.
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.