LowestCommonAncestorOfABinaryTree [source code]

public class LowestCommonAncestorOfABinaryTree {
static
/******************************************************************************/
class Solution {
    boolean found = false;
    TreeNode lca = null;

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        postOrder (root, p, q);
        return lca;
    }

    int postOrder (TreeNode root, TreeNode p, TreeNode q) {
        int res = 0;
        if (root == null)
            return res;
        int left = postOrder (root.left, p, q);
        if (found)
            return res;
        int right = postOrder (root.right, p, q);
        // pre-leaf pruning is safer here
        if (found)
            return res;
        res = left | right;
        if ((res > 0 && (root == p || root == q)) || (left ^ right) == 0b11) {
            found = true;
            lca = root;
            return res;
        }
        if (root == p)
            res |= 02;
        if (root == q)
            res |= 01;
        return res;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        LowestCommonAncestorOfABinaryTree.Solution tester = new LowestCommonAncestorOfABinaryTree.Solution();
    }
}

很有意思的一个题目, Yahoo电面的时候碰到的是简化版本(BST版本), 那个其实很好些, 笨办法就是把两个node的path全都写下来, 然后比较prefix就行了; 聪明办法就是直接一个pass, 从上到下走, 第一个node that can split A and B on either side, 就是LCA;

相比之下, 这个general版本的还是有点难度的; 思考的时候用的是这个例子:

00 00 -> 00  
01 00 -> 01  
10 00 -> 10  
01 10 -> found : 11  
11 00 -> 11

大概能够发现这题用位运算来做好像可能会快一点;

注意, 上面的代码实际上是优化过一次的, 第一次AC的代码其实是这个:

class Solution {  
    boolean found = false;  
    TreeNode lca = null;  

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {  
        postOrder (root, p, q);  
        return lca;  
    }  

    int postOrder (TreeNode root, TreeNode p, TreeNode q) {  
        int res = 0;  
        if (root == null)  
            return res;  
        int left = postOrder (root.left, p, q);  
        if (found)  
            return res;  
        int right = postOrder (root.right, p, q);  
        if (found)  
            return res;  
        res = left | right;  
        if ((left ^ right) == 0b11) {  
            found = true;  
            lca = root;  
        }  
        if (root == p) {  
            if (res > 0) {  
                found = true;  
                lca = root;  
                return res;  
            }  
            res |= 02;  
        }  
        if (root == q) {  
            if (res > 0) {  
                found = true;  
                lca = root;  
                return res;  
            }  
            res |= 01;  
        }  
        return res;  
    }  
}

真正面试的时候不要太纠结漂亮, 写出来才是最有用的;

Recursion is actually bottom-up

思路的话自己画画图应该不难理解; 核心就是要理解DFS这个recursion, 本身其实是一个Bottom-Up从下到上的过程; 从下到上的过程中, 你碰到的第一个subroot that contains A on one side and B on the other就行了, 就是LCA; 当然还要考虑AB当中一个是另外一个的descendant的特殊情况, 不过again, 一定要记得从typical 例子开始分析;

pre-leaf or leaf

又是这个老生常谈的话题, 注意, 这题用pre的做法要比用leaf的做法简单很多; 我尝试了一下改成leaf判断的做法(因为代码会清秀一些), 但是最后发现完全不是那么容易的; 最近在看Sedgwick, 也是发现他很擅长在该用pre处理base case的时候就用pre;

另外, 我这里说的这个判断, 针对的实际上是found这个global switch pruning的判断; 忘记交代了;

UNFINISHED

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 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.

Difficulty:Medium
Total Accepted:161.4K
Total Submissions:539.5K
Contributor:LeetCode
Companies
facebookmicrosoftamazonlinkedinapple
Related Topics
tree
Similar Questions
Lowest Common Ancestor of a Binary Search Tree