First Common Ancestor

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

Solution

如果有指向父节点的指针,那么就一直上溯,直到找到一样的父节点。如果没有指向父节点的指针,那么从根节点开始用DFS选择性的进行搜索:如果这两个节点都在某个节点的左子树中,那么解一定在此节点的左子树中;类似的,如果两个节点都在某个节点的右子树中,那么解一定在此节点的右子树中。换言之,所求的解一定将给定的两个节点分别分割在左右子树中。

那么,我们可以用一个辅助函数来判断一个节点是否隶属于子树。在主函数中,从根开始判断两个节点是否处于同一边的子树:如果是,那么所求的解一定属于该子树, 我们可以沿子树方向再往下走一层;如果不是,那么当前根就是答案。

Complexity

假设树高度为h,对于第i层,判断两个节点是否分别处于不同子树需要搜索2h-i次。整体复杂度为:1 + 2 + 22 + … + 2h, 即O(2h+1)。


时间 O(h) 空间 O(h) 递归栈空间

思路

我们可以用深度优先搜索,从叶子节点向上,标记子树中出现目标节点的情况。如果子树中有目标节点,标记为那个目标节点,如果没有,标记为null。显然,如果左子树、右子树都有标记,说明就已经找到最小公共祖先了。如果在根节点为p的左右子树中找p、q的公共祖先,则必定是p本身。

换个角度,可以这么想:如果一个节点左子树有两个目标节点中的一个,右子树没有,那这个节点肯定不是最小公共祖先。如果一个节点右子树有两个目标节点中的一个,左子树没有,那这个节点肯定也不是最小公共祖先。只有一个节点正好左子树有,右子树也有的时候,才是最小公共祖先。

Code

Node commonAncestor(Node root, Node node1, Node node2){
    if (root == null || node1 == null || node2 == null) return null;
    
    if (covers(root.left, node1) && covers(root.left, node2)){
        return commonAncestor(root.left, node1, node2);
    }
    if (covers(root.right, node1) && covers(root.right, node2)){
        return commonAncestor(root.right, node1, node2);
    }
    return root;
}


boolean covers(Node root, Node node){
    if (root == null) return false;
    if (root == node) return true;
    
    return covers(root.left, node) || covers(root.right, node);
}

来自 CC 的分析与解答

/**
 * Solution #1: With Links to Parents
 *
 * We could trace just p's path upwards. At each node on this path, check to
 * see if this node is on the path from q to the root. The first such node
 * will be the first common ancestor.
 */

TreeNode commonAncestor(TreeNode p, TreeNode q){
    if (p == q) return null;

    TreeNOde ancestor = p;
    while (ancestor != null){
        if (isOnPath(ancestor, q)){
            return ancestor;
        }
        ancestor = ancestor.parent;
    }
    return ull;
}

boolean isOnPath(TreeNode ancestor, TreeNode node){
    while (node != ancestor && node != null){
        node = node.parent;
    }
    return node == ancestor;
}


/**
 * Solution #2: With Links to Parents(Better worst case runtime)
 * We can just traverse upwards from p, storing the parent and the sibling
 * node in a variable. (The sibling node is always a child of parent and
 * refers to the newly uncovered subtree.) At each iteration, sibling gets
 * set to the old parent's sibling node and parent gets set to parent.parent.
 */

TreeNode commonAncestor(TreeNode root, TreeNode p, TreeNode q){
    if (!covers(root, p) || !covers(root, q)){
        return null;
    }
    else if (covers(p, q)){
        return p;
    }
    else if (covers(q, p)){
        return q;
    }

    TreeNode sibling = getSibling(p);
    TreeNode parent = p.parent;
    while (!covers(sibling, q)){
        sibling = getSibling(parent);
        parent = parent.parent;
    }
    return parent;
}

boolean covers(TreeNode root, TreeNode p){
    if (root == null) return false;
    if (root == p) return true;
    return covers(root.left, p) || covers(root.right, p);
}

TreeNode getSibling(TreeNode node){
    if (node == null || node.parent == null){
        return null;
    }

    TreeNode parent = node.parent;
    return parent.left == node ? parent.right : parent.left;
}


/**
 * Solution #3: Without Links to Parents
 *
 * You could follow a chain in which p and q are on the same side. That is,
 * if p and q are both on the left of the node, branch left to look for the
 * common ancestor. If they are both on the right, branch right to look for
 * the common ancestor. When p and q are no longer on the same side, you
 * must have found the first common ancestor.
 */

TreeNode commonAncestor(TreeNode root, TreeNode p, TreeNode q){
    if (!covers(root, p) || !covcers(root, q)){
        return null;
    }
    return ancestorHelper(root, p, q);
}

TreeNode ancestorHelper(TreeNode root, TreeNode p, TreeNode q){
    if (root == null){
        return null;
    }
    else if (root == p){
        return p;
    }
    else if (root == q){
        return q;
    }

    boolean pIsOnLeft = covers(root.left, p);
    boolean qIsOnLeft = covers(root.left, q);
    if (pIsOnLeft != qIsOnleft){
        return root;
    }
    TreeNode childSide = pIsOnLeft ? root.left : root.right;
    return ancestorHelper(childSide, p, q);
}

boolean covers(TreeNode root, TreeNode p){
    if (root == null) return false;
    if (root == p) return true;
    return covers(root.left, p) || covers(root.right, p);
}