236. Lowest Common Ancestor of a Binary Tree

problem description

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Given the following binary tree: root = [3,5,1,6,2,0,8,null,null,7,4]

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

Example 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

algorithm thought

这题是上题的进阶，这里的树不再是BST，不是BST的话，TreeNode里的val节点就对我们没啥用了。这里也必须遍历所有节点才能找到最小公共祖先。

这里用递归来做，从根节点开始，首先在它的左子树进行一次寻找，如果找到p或者找到q，就会有个返回值，如果都没找到，返回NULL。在右子树进行同理查找方式。最后两个查找结束之后，返回到根节点检查。如果两个返回都不是NULL，说明两个节点分别出现在两个子树，这时候根节点是公共节点，返回根。如果只有一个子树返回了，说明两个节点都在那个子树中，这里直接返回那个值即可。如果两个都是NULL节点，返回NULL。

code

/**
 * 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||root==p||root==q)
            return root;
        TreeNode*le=lowestCommonAncestor(root->left,p,q);
        TreeNode*ri=lowestCommonAncestor(root->right,p,q);
        if(le==NULL)
            return ri;
        else{
            if(ri==NULL)
                return le;
            else
                return root;
        }
    }
};

algorithm analysis

这里和上题不同的地方在于，这里需要将树都遍历一遍。时间复杂度O(n)