236. Lowest Common Ancestor of a Binary Tree

解題思路

會有兩種情況： p, q 屬於同一個 subtree 或不是。如果不是，那麼回傳的就會是他們的再往上的 root，不然就是 p 跟 q 自己。

判斷方法就是一直往下看左右子樹有沒有 p 跟 q，如果有的話就回傳那個 node，如果沒有就是回傳 root。

程式碼

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 root;
        else if(left != nullptr)
            return left;
        else
            return right;
    }
};