236. 二叉樹的最近公共祖先

思路

程式碼

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* node, TreeNode* p, TreeNode* q) {        
        if(!node || node == p || node == q) return node;
        TreeNode* left = lowestCommonAncestor(node->left, p, q);
        TreeNode* right = lowestCommonAncestor(node->right, p, q);
        if(!left && !right) return nullptr; // 都沒有找到, 把空往上傳
        if(left && right) return node; // 左邊有找到, 右邊也有找到, 自己就是祖先
        // 現在只有一個是空的, 返回不是空的那一邊
        return !left ? right : left;
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：棧空間 $O(\log{n})$