Lowest Common Ancestor of a Binary Tree

Leave a comment

October 30, 2016 by oneOokay

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


Sept 11, 2017.

纠结在recursive的解法里面,默认了两个given node都是存在于tree里面的. 当只找到p和q之间的一个的时候,recursive就会返回.所以其中的一个返回了p值,另一个返回是null. 其实并没有真正的找到q.这样是默认的q在返回的p的子树里(因为默认它存在于树中,recursive进行到这里说明它不存在另一个子树里面所以必然存在p的子树里面).

如果想要更加完善的话, 加入isNodePresent method.

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return root;
        if (isNodePresent(root, p) && isNodePresent(root, q)){
            return helper(root, p, q);
        }
        return null;
    }
    
    private boolean isNodePresent(TreeNode root, TreeNode n){
        if (root == null) return false;
        if (root == n) return true;
        return isNodePresent(root.left, n) || isNodePresent(root.right, n);
    }
    
    private TreeNode helper(TreeNode root, TreeNode p, TreeNode q){
        if (root == null) return root;
        if (root == p || root == q) return root;
//从root向左路径一直向下,直到null或者找到其中一个叶子节点为止
        TreeNode left = helper(root.left, p, q);
//从root向右路径一直向下,直到null或者找到其中一个叶子节点为止
        TreeNode right = helper(root.right, p, q);
//同时找到了两个目标节点, 那么该root就为他们的LCA return root;
        if (left != null && right != null) return root;
//从root向左路径往下只找到了一个目标节点, 从root向右路径往下没有找到另一个节点: 
//说明另一个节点一定是在左路径的那个节点下的子节点,所以LCA为left
        if (left != null) return left;
        if (right != null) return right;//同左
        return null;
    }

Divide & Conquer:

Divide & Conquer 成功写到了left和right那里,然后就没了=。=所以还是要熟悉递归到最后归出来的到底是什么。

如何看递归到最后归出来的是什么呢?

  1. 调用原LCA函数的时候,left=用了LCA(root.left, p, q):说明每次recrusive都是往一个点的最左儿子下去走的,起点为root。
  2. 再看LCA的返回值的情况:只有在遇到左儿子等于p或者q的时候返回p,q;或者没有找到p,q返回null
  3. 结合在一起看的话这个recursive就是一条从root出发,在root的左子树中找q,p的一条路径。
  4. 所以同理right = LCA(root.right, p,q)是找到一条从root出发在root的右子树中找qp的一条路径
  5. 到最后对left和right进行判定就能够得出LCA了:如果left和right都存在的话,说明q,p处于root的左右两个子树上,所以他们的LCA是root;如果left和right只有一个存在的话,说明p,q处于root的左子树或者右子树上;所以他们的LCA是root.left或者root.right;如果left和right都不存在的话,说明并没有找到;于是返回null。

NON Recursive / ITERATIVE的做法:

  1. 遍历tree来找到p和q;这里随便用什么遍历方法. 目的仅仅在于维持一个parent/child map和找到pq而已. 所以可以用stack也可以用queue
  2. 遍历的同时构建一个parent的hashmap<TreeNode, TreeNode>: hashmap<node, node的parent>.
  3. 同时找到了p和q之后层遍历停止。
  4. 接下来通过之前构建的parent hashmap,从p”由下往上”找出从p到root的一个路径。
  5. 最后一步是对于q“由下往上”找,找到在之前p路径中第一个相同的元素。该元素为两者的LCA。

BST (Binary Search Tree) LCA


Oct 30:

我又睡了十个多小时=。= 最近好累啊

  • Lowest Common Ancestor of a Binary Tree
  • Lowest Common Ancestor of a Binary Search Tree

Tree那边刚好刷到这个LCA:普通LCA。 BST LCA在后面

Iterative

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
 if (root == null) return null;
 HashMap<TreeNode, TreeNode> map = new HashMap<>();
 Stack<TreeNode> stack = new Stack<>();
 stack.push(root);
 map.put(root, null);
 TreeNode tmp = null;
 while (!map.containsKey(p) || !map.containsKey(q)){
 if (stack.isEmpty()) break;
 tmp = stack.pop();
 if (tmp.left != null){
 stack.push(tmp.left);
 map.put(tmp.left, tmp);
 }
 
 if (tmp.right != null){
 stack.push(tmp.right);
 map.put(tmp.right, tmp);
 }
 }
 if (stack.isEmpty() && (!map.containsKey(q) || !map.containsKey(p))){
 return null;
 }
 Set<TreeNode> path = new HashSet<>();
 tmp = p;
 while (tmp != null){
 path.add(tmp);
 tmp = map.get(tmp);
 }
 tmp = q;
 while(!path.contains(tmp)){
 tmp = map.get(tmp);
 }
 return tmp;
 }
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: