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.


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. 层遍历来找到p和q;(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在后面。

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

2. 非递归解法:

public class Solution {
 public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
 HashMap<TreeNode, TreeNode> parent = new HashMap<TreeNode, TreeNode>();
 Queue queue = new LinkedList();//层遍历用queue
 parent.put(root, null);
 queue.offer(root);
 while (!parent.containsKey(p) || !parent.containsKey(q)){
 TreeNode node = queue.poll();
 if (node.left != null){
 queue.offer(node.left);
 parent.put(node.left, node);
 }
 if (node.right != null){
 queue.offer(node.right);
 parent.put(node.right, node);
 }
 }//遍历完毕找到pq且构建好了parent mapping
 
 Set set = new HashSet();
 while (p != null){
 set.add(p);
 p = parent.get(p);
 }//构建p的一条路径
 
 while (!set.contains(q)){
 q = parent.get(q);
 }//寻找q路径上第一个与p路径重合的点
 return q;
 }
}
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: