236 - Lowest Common Ancestor of a Binary Tree

Lowest Common Ancestor of a Binary Tree

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 v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Hide Tags

 Tree

Hide Similar Problems

 (E) Lowest Common Ancestor of a Binary Search Tree

一个做法是从上而下，每个点检查，
如果这个点是LCA，那么一定左右子节点同时能找到两个指定点（具体哪个在哪边无所谓）
不然的话，只在左或者右子节点同时找到，那么该子节点才是LCA
实现参见 https://leetcode.com/discuss/45929/very-simple-dfs-c-solution-only-10-lines 

另一个法子是，先找到第一个点，把路径存下来，
然后只要从后往前检查这些保存了的点，第一个能dfs到另一个点的就是LCA。

注意可能有重复的值，所以比较要用指针，不要用值。

这两个方法实际上核心想法是一样的，找到一个，回退，找第二个，第一种代码更简洁。
基于第二个想法的实现：

/**

 * 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) {

        TreeNode* lca = NULL;

        if(root)

        {

            vector<TreeNode*> checklist;

            TreeNode* unlocated = NULL;

            //这里的写法是locate p 或 q 中的一个，把另一个作为unlocated
            //当然也可以简化成直接locate p，而后处理q

            locateA(root, p, q, unlocated, checklist);

            

            lca = locateB(checklist, unlocated);

        }

        return lca;

    }

private:    

    bool locateA(TreeNode* root, TreeNode* p, TreeNode* q, TreeNode*& unlocated, vector<TreeNode*>& checklist)

    {

        bool ret = true;

        if(root == p)//((root->val) == (p->val))

            unlocated = q;

        else if(root == q)//((root->val) == (q->val))

            unlocated = p;

        else if((NULL==root->left)&&(NULL==root->right))

            ret = false;

        else

        {

        ret = false;

            if(root->left)

                ret = locateA(root->left, p, q, unlocated, checklist);

            

            if((false==ret)&&(root->right))

                 ret = locateA(root->right, p, q, unlocated, checklist);

        }

        if(true == ret)

            checklist.push_back(root);

        return ret;

    }

    TreeNode* locateB(vector<TreeNode*> checklist, TreeNode* unlocated)

    {

        int sz=checklist.size();

        for(int ii=0; ii<sz; ++ii)

        {

            if(true == dfs(checklist[ii], unlocated))

                return checklist[ii];

        }

        return NULL;

    }

    bool dfs(TreeNode* root, TreeNode* leaf)

    {

        if(root == leaf)//((root->val)==(leaf->val))

            return true;

        else if((NULL==root->left)&&(NULL==root->right))

            return false;

        else

        {

            if(root->left)

                if(true == dfs(root->left, leaf))

                    return true;

            

            if(root->right)

                if(true == dfs(root->right, leaf))

                    return true;

        }

        return false;

    }

};

24 ms.