236. Lowest Common Ancestor of a Binary Tree

1.問題

• 給予一個binary tree, 找出Lowest Common Ancestor (LCA)

2.想法

• 這題與235. Lowest Common Ancestor of a Binary Search Tree類似, 但差別在於235是在BST上面搜尋, 可以利用BST的特性來撰寫演算法, 但這題少了這個特性可以使用, 因此需要不同的算法

• 可以使用DFS

  • 每次函式會呼叫自己並將root的左右子代當成新的root(新的左右函式), 目的是搜尋p, q

  • 當函式中的root等於p, q時, 代表搜尋到了, 並開始return

  • 當新的左右函式皆有回傳值時, 該次的root即為所求

3.程式碼

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == NULL)
        {
            return NULL;
        }
        
        if (root == p || root == q)
        {
            return root;
        }
        
        TreeNode* leftLCA = lowestCommonAncestor(root->left, p, q);
        TreeNode* rightLCA = lowestCommonAncestor(root->right, p, q);
        
        if (leftLCA != NULL && rightLCA != NULL)
        {
            return root;
        }
        
        if (leftLCA != NULL)
        {
            return leftLCA;
        }
        return rightLCA;
        
    }
};

4.Performance