`
java-mans
  • 浏览: 11340508 次
文章分类
社区版块
存档分类
最新评论

最近公共祖先 (LCA) [No. 21]

 
阅读更多

问题:

给定一个二叉树,找到两个节点NA, NB的最近公共祖先(LCA)。

比如对于下图,4 和 7 的 LCA 是6, 1和13的LCA 是 8。


我们这里先考虑一般的二叉树(BT),然后再考虑这个二叉树是二叉搜索树(BST)的情况。

查找两个node的最早的公共祖先,分三种情况:
1. 如果两个node在root的两边,那么最早的公共祖先就是root。
2. 如果两个node在root的左边,那么把root.leftChild作为root,再递归。
3.如果两个node在root的右边,那么把root.rightChild作为root,再递归。
那么我们如何知道能否通过原始节点到达某一个节点呢?这里我们需要定义一个递归函数covers (Node root, Node node),让root的左右子节点不断的调用这个函数,如果某一个子节点就是要找到的节点,那么返回true,否则返回false. 具体代码如下:
/*
     * check whether the node n is in the tree
     */
    private static boolean covers(Node rootNode, Node n) {
    	if(rootNode == null) return false;
    	if(rootNode == n) return true;
    	return covers(rootNode.leftChild, n) || covers(rootNode.rightChild, n);
    }
有个covers这个函数,我们要实现前面三种不同的情况,那就简单了。代码如下:
/*
     * get the first common ancestor of node p and node q
     */
    public static Node commonAncestor(Node rootNode, Node p, Node q) {
    	// case 2
        if (covers(rootNode.leftChild, p) && covers(rootNode.leftChild, q))
    		return commonAncestor(rootNode.leftChild, p, q);
    	//case 3
        if (covers(rootNode.rightChild, p) && covers(rootNode.rightChild, q))
    		return commonAncestor(rootNode.rightChild, p, q);
    	//case 1
        return rootNode;
    }

如果这个二叉树是BST,那么我们可以利用BST的特点,把根节点的值与两个节点的值进行比较,如果两个节点的值都比节点的值小,那么一定在节点的左边,所以我们把节点的左子节点作为起始点,然后递归。如果两个节点的值都比祖先节点的值大,那么一定在节点的右边,所以我们把节点的右子节点作为起始点,然后递归,如果上面两张情况都不是,那么很明显,这个节点就是LCA. 代码如下:
public Node LCA(Node root, Node p, Node q) {
  if (root == null || p == null || q == null ) return NULL;	
  if (max(p.data, q.data) < root.data)
    return LCA(root.left, p, q);
  else if (min(p.data, q.data) > root.data)
    return LCA(root.right, p, q);
  else
    return root;
}
备注:这里并没有考虑 p 和 q 不在 BST里的情况。

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics