Lowest Common Ancestor of a Binary Tree Part I | LeetCode
http://www.geeksforgeeks.org/lowest-common-ancestor-binary-tree-set-1/
http://www.geeksforgeeks.org/lowest-common-ancestor-binary-tree-set-1/
Given a binary tree, find the lowest common ancestor of two given nodes in the tree.
X.
_______3______
/ \
___5__ ___1__
/ \ / \
6 _2 0 8
/ \
7 4
For example, the lowest common ancestor (LCA) of nodes
X. https://www.cnblogs.com/grandyang/p/4641968.html
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.X. https://www.cnblogs.com/grandyang/p/4641968.html
这道求二叉树的最小共同父节点的题是之前那道 Lowest Common Ancestor of a Binary Search Tree 的Follow Up。跟之前那题不同的地方是，这道题是普通是二叉树，不是二叉搜索树，所以就不能利用其特有的性质，所以我们只能在二叉树中来搜索p和q，然后从路径中找到最后一个相同的节点即为父节点，我们可以用递归来实现，在递归函数中，我们首先看当前结点是否为空，若为空则直接返回空，若为p或q中的任意一个，也直接返回当前结点。否则的话就对其左右子结点分别调用递归函数，由于这道题限制了p和q一定都在二叉树中存在，那么如果当前结点不等于p或q，p和q要么分别位于左右子树中，要么同时位于左子树，或者同时位于右子树，那么我们分别来讨论：
若p和q要么分别位于左右子树中，那么对左右子结点调用递归函数，会分别返回p和q结点的位置，而当前结点正好就是p和q的最小共同父结点，直接返回当前结点即可，这就是题目中的例子1的情况。
若p和q同时位于左子树，这里有两种情况，一种情况是left会返回p和q中较高的那个位置，而right会返回空，所以我们最终返回非空的left即可，这就是题目中的例子2的情况。还有一种情况是会返回p和q的最小父结点，就是说当前结点的左子树中的某个结点才是p和q的最小父结点，会被返回。
若p和q同时位于右子树，同样这里有两种情况，一种情况是right会返回p和q中较高的那个位置，而left会返回空，所以我们最终返回非空的right即可，还有一种情况是会返回p和q的最小父结点，就是说当前结点的右子树中的某个结点才是p和q的最小父结点，会被返回，写法很简洁
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);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left != null && right != null) return root;
return left == null ? right : left;
上述代码可以进行优化一下，如果当前结点不为空，且既不是p也不是q，那么根据上面的分析，p和q的位置就有三种情况，p和q要么分别位于左右子树中，要么同时位于左子树，或者同时位于右子树。我们需要优化的情况就是当p和q同时为于左子树或右子树中，而且返回的结点并不是p或q，那么就是p和q的最小父结点了，已经求出来了，就不用再对右结点调用递归函数了
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if (!root || p == root || q == root) return root; TreeNode *left = lowestCommonAncestor(root->left, p, q); if (left && left != p && left != q) return left; TreeNode *right = lowestCommonAncestor(root->right, p , q); if (left && right) return root; return left ? left : right; }http://www.jiuzhang.com/solutions/lowest-common-ancestor/
Version 1: Traditional Method， 如果有父亲节点 private ArrayList<TreeNode> getPath2Root(TreeNode node) { ArrayList<TreeNode> list = new ArrayList<TreeNode>(); while (node != null) { list.add(node); node = node.parent; } return list; } public TreeNode lowestCommonAncestor(TreeNode node1, TreeNode node2) { ArrayList<TreeNode> list1 = getPath2Root(node1); ArrayList<TreeNode> list2 = getPath2Root(node2); int i, j; for (i = list1.size() - 1, j = list2.size() - 1; i >= 0 && j >= 0; i--, j--) { if (list1.get(i) != list2.get(j)) { return list1.get(i).parent; } } return list1.get(i+1); }
A modified version of pre-order traversal. The point to understand this is, once a sub-branch has a possible ancestor, all its super branches will have the same one.
我们可以用深度优先搜索，从叶子节点向上，标记子树中出现目标节点的情况。如果子树中有目标节点，标记为那个目标节点，如果没有，标记为null。显然，如果左子树、右子树都有标记，说明就已经找到最小公共祖先了。如果在根节点为p的左右子树中找p、q的公共祖先，则必定是p本身。
换个角度，可以这么想：如果一个节点左子树有两个目标节点中的一个，右子树没有，那这个节点肯定不是最小公共祖先。如果一个节点右子树有两个目标节点中的一个，左子树没有，那这个节点肯定也不是最小公共祖先。只有一个节点正好左子树有，右子树也有的时候，才是最小公共祖先。
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//发现目标节点则通过返回值标记该子树发现了某个目标结点
if(root == null || root == p || root == q) return root;
//查看左子树中是否有目标结点，没有为null
TreeNode left = lowestCommonAncestor(root.left, p, q);
//查看右子树是否有目标节点，没有为null
TreeNode right = lowestCommonAncestor(root.right, p, q);
//都不为空，说明做右子树都有目标结点，则公共祖先就是本身
if(left!=null&&right!=null) return root;
//如果发现了目标节点，则继续向上标记为该目标节点
return left == null ? right : left;
}Version 2: Divide & Conquer // 在root为根的二叉树中找A,B的LCA: // 如果找到了就返回这个LCA // 如果只碰到A，就返回A // 如果只碰到B，就返回B // 如果都没有，就返回null public TreeNode lowestCommonAncestor(TreeNode root, TreeNode node1, TreeNode node2) { if (root == null || root == node1 || root == node2) { return root; } // Divide TreeNode left = lowestCommonAncestor(root.left, node1, node2); TreeNode right = lowestCommonAncestor(root.right, node1, node2); // Conquer if (left != null && right != null) { return root; } if (left != null) { return left; } if (right != null) { return right; } return null; }http://www.programcreek.com/2014/07/leetcode-lowest-common-ancestor-of-a-binary-tree-java/
class Entity{ public int count; public TreeNode node; public Entity(int count, TreeNode node){ this.count = count; this.node = node; } } public class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { return lcaHelper(root, p, q).node; } public Entity lcaHelper(TreeNode root, TreeNode p, TreeNode q){ if(root == null) return new Entity(0, null); Entity left = lcaHelper(root.left, p, q); if(left.count==2) return left; Entity right = lcaHelper(root.right,p,q); if(right.count==2) return right; int numTotal = left.count + right.count; if(root== p || root == q){ numTotal++; } return new Entity(numTotal, root); } }
X.
https://leetcode.com/discuss/64764/java-python-iterative-solution
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
Map<TreeNode, TreeNode> parent = new HashMap<>();
Deque<TreeNode> stack = new ArrayDeque<>();
parent.put(root, null);
stack.push(root);
while (!parent.containsKey(p) || !parent.containsKey(q)) {
TreeNode node = stack.pop();
if (node.left != null) {
parent.put(node.left, node);
stack.push(node.left);
}
if (node.right != null) {
parent.put(node.right, node);
stack.push(node.right);
}
}
Set<TreeNode> ancestors = new HashSet<>();
while (p != null) {
ancestors.add(p);
p = parent.get(p);
}
while (!ancestors.contains(q))
q = parent.get(q);
return q;
}
https://leetcode.com/discuss/50968/build-paths-stacks-nodes-return-first-crossing-point-paths
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { Stack<TreeNode> pStack = new Stack<TreeNode>(); Stack<TreeNode> qStack = new Stack<TreeNode>(); TreeNode target = null; if (findPath(root, p, pStack) && findPath(root, q, qStack)) { while (!pStack.isEmpty()) { TreeNode pNode = pStack.pop(); if (qStack.contains(pNode)) target = pNode; } } return target; } private boolean findPath(TreeNode root, TreeNode node, Stack<TreeNode> stack) { if (root == null) return false; if (root == node) { stack.push(root); return true; } else { if (findPath(root.left, node, stack) || findPath(root.right, node, stack)) { stack.push(root); return true; } } return false; }
http://blog.csdn.net/xudli/article/details/46871283
A Bottom-up Approach (Worst case O(n) ): Post-Order Traversal
A Top-Down Approach (Worst case O(n2) ):
http://wp.javayu.me/2014/02/lowest-common-ancestor-of-a-binary-tree/
在访问到leaf后结果按照bottom-up的方式向上传递。之前top-down approach是每次都检查两边的子树，然后进入一棵，再检查其子树，重复的部分在于：子树可能被多次check。而通过bottom-up的方式，信息流只需要一次就能到位.
算法优化，如果有多次重复问题的情况下，找出每次重复之间的重复子问题关系，寻找合适的信息流向让计算更快捷
树的recursive算法不一定要先判断当前节点再判断子树，如果子树的信息对于当前节点有用，则可以颠倒顺序变成bottom-up的方式
树的bottom-up方式和top-down方式的主要差别就在于：先处理当前节点还是先处理子树
recursion时，返回的值不一定要是最终的是否判断。也可以返回其他包含信息量更多的内容。
http://www.code123.cc/docs/leetcode-notes/binary_tree/lowest_common_ancestor.html
自底向上(计数器)
我们可以对返回结果添加计数器来解决。
定义pair result(node, counter)表示遍历到某节点时的返回结果，返回的node表示LCA 路 径中的可能的最小节点，相应的计数器counter则表示目前和A或者B匹配的节点数，若计数器为2，则表示已匹配过两次，该节点即为所求，若只匹配过一 次，还需进一步向上递推。表述地可能比较模糊，还是看看代码吧。
/* Error check - one node is not in the tree. */
if (!covers(root, p) || !covers(root, q)) {
return null;
}
return ancestorHelper(root, p, q);
}
TreeNode ancestorHelper(TreeNode root, TreeNode p, TreeNode q) {
if (root== null || root== p || root== q) {
return root;
}
boolean plsOnleft = covers(root.left, p);
boolean qlsOnLeft = covers(root.left, q);
if (plsOnLeft != qlsOnLeft) {//Nodes are on different side
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);
}
there is still some inefficiency in how it operates. Specifically, covers searches all nodes under root for p and q, including the nodes in each subtree (root. left and root. right). Then, it picks one of those subtrees and searches all of its nodes. Each subtree is searched over and over again.
class Result {
public TreeNode node;
public boolean isAncestor;
public Result(TreeNode n, boolean isAnc) {
node = n;
isAncestor = isAnc;
}
}
TreeNode commonAncestor(TreeNode root, TreeNode p, TreeNode q) {
Result r = commonAncestorHelper(root, p, q);
if (r.isAncestor) {
return r.node;
}
return null;
}
Result commonAncHelper(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) return new Result(null, false);
if (root==p && root== q) {
return new Result(root, true);
}
Result rx = commonAncHelper(root.left, p, q);
if (rx.isAncestor) {//Found common ancestor
return rx;
}
Result ry = commonAncHelper(root.right, p, q);
if (ry.isAncestor) {//Found common ancestor
return ry;
}
if (rx.node != null && ry.node != null) {
return new Result(root, true); // This is the common ancestor
} else if (root == p || root == q) {
/* If we're currently at p or q, and we also found one of those nodes in a
* subtree, then this is truly an ancestor and the flag should be true. */
boolean isAncestor = rx.node != null I I ry.node != null;
return new Result(root, isAncestor);
} else {
return
new Result(rx.node!=null ? rx.node ry.node, false);
}
}
TreeNode commonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root null) return null;
if (root == p && root == q) return root;
TreeNode x = commonAncestor(root.left, p, q);
if (x != null && x != p && x != q) {
// Already found ancestor
return x;
}
TreeNode y = commonAncestor(root.right, p, q);
if (y != null && y != p && y != q) { // Already found ancestor
return y;
}
if (x != null && y != null) { // p and q found in diff.subtrees
return root; II This is the common ancestor
} else if (root == p I I root == q) {
return root;
} else {
return x == null ? y x; I* return the non-null value *I
}
}
https://www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor/
http://blog.csdn.net/fightforyourdream/article/details/20441629
http://www.fusu.us/2013/06/p2-lowest-common-ancestor-in-binary-tree.html
https://github.com/mintycc/OnlineJudge-Solutions/blob/master/Leetcode/236_Lowest_Common_Ancestor_of_a_Binary_Tree.java
1. DFS或⼀一个不不在树里 O(n) (code)
2. General Tree，⾮非
⼆二叉 (code)
3. Parent node + Set: O(h) (code)
4. Path + BinarySearch O(n^2 + klogn)
5. Doubling Algorithm O(nlogn + klogn) 过 难了了
6. Tarjan 吹⽜牛逼
1. 如果每个node包含parent指针 (向上parent直到root，⽤用set找重复路路径)
2. 假设node的值不不重复，但node没有parent pointer。给出了了O(n)的解，
n是binary tree中node的数量量。(a.HashMap储存parent关系 b.遍历binary
tree，找出2个node到root的path然后⽐比较 c. O(n^2)预处理理找出所有path
或者O(nlogn)倍增，然后BinarySearch找相同前缀)
3. follow up 是如果有⼀一个treenode 不不在树⾥里里应该怎么做 (helper函数
+Single返回值);之后的follow up是设计⼀一个存储结构，使得搜索只需要
O(lg(n))时间 (a.O(n^2)预处理理找出所有path然后BinarySearch b.O(nlogn)
倍增);
4. 找⼀一个general树的LCA
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/discuss/187535/Python-
To find the lowest common ancestor, we need to find where is
p and q and a way to track their ancestors. A parent pointer for each node found is good for the job. After we found both p andq, we create a set of p's ancestors. Then we travel through q's ancestors, the first one appears in p's is our answer.https://leetcode.com/discuss/50968/build-paths-stacks-nodes-return-first-crossing-point-paths
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { Stack<TreeNode> pStack = new Stack<TreeNode>(); Stack<TreeNode> qStack = new Stack<TreeNode>(); TreeNode target = null; if (findPath(root, p, pStack) && findPath(root, q, qStack)) { while (!pStack.isEmpty()) { TreeNode pNode = pStack.pop(); if (qStack.contains(pNode)) target = pNode; } } return target; } private boolean findPath(TreeNode root, TreeNode node, Stack<TreeNode> stack) { if (root == null) return false; if (root == node) { stack.push(root); return true; } else { if (findPath(root.left, node, stack) || findPath(root.right, node, stack)) { stack.push(root); return true; } } return false; }
Similar solution with some trival improvements.
- call findPath function just once.
- search the target Treenode from the beginning of two lists, because the time complexity of contains functions is O(n).
- use label as a flag variable, which indicates when we can exit early.
http://blog.csdn.net/xudli/article/details/46871283
如果是普通二叉树, 而不是BST. 则应该遍历节点, 先找到p,q. 同时记录下从root到该几点的路径. 之后比较路径,最后一个相同的节点便是LCA.
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==null || p==null || q==null) return null;
List<TreeNode> pathp = new ArrayList<>();
List<TreeNode> pathq = new ArrayList<>();
pathp.add(root);
pathq.add(root);
getPath(root, p, pathp);
getPath(root, q, pathq);
TreeNode lca = null;
for(int i=0; i<pathp.size() && i<pathq.size(); i++) {
if(pathp.get(i) == pathq.get(i)) lca = pathp.get(i);
else break;
}
return lca;
}
private boolean getPath(TreeNode root, TreeNode n, List<TreeNode> path) {
if(root==n) {
return true;
}
if(root.left!=null) {
path.add(root.left);
if(getPath(root.left, n, path)) return true;
path.remove(path.size()-1);
}
if(root.right!=null) {
path.add(root.right);
if(getPath(root.right, n, path)) return true;
path.remove(path.size()-1);
}
return false;
}
Method 1 (By Storing root to n1 and root to n2 paths): Get the first different value.
树中两个结点的最低公共祖先
Following is simple O(n) algorithm to find LCA of n1 and n2.
1) Find path from root to n1 and store it in a vector or array.
2) Find path from root to n2 and store it in another vector or array.
3) Traverse both paths till the values in arrays are same. Return the common element just before the mismatch.
树中两个结点的最低公共祖先
Following is simple O(n) algorithm to find LCA of n1 and n2.
1) Find path from root to n1 and store it in a vector or array.
2) Find path from root to n2 and store it in another vector or array.
3) Traverse both paths till the values in arrays are same. Return the common element just before the mismatch.
The tree is traversed twice, and then path arrays are compared.
This method finds LCA in O(n) time, but requires three tree traversals plus extra spaces for path arrays.
// Finds the path from root node to given root of the tree, Stores the// path in a vector path[], returns true if path exists otherwise falsebool findPath(Node *root, vector<int> &path, int k){ // base case if (root == NULL) return false; // Store this node in path vector. The node will be removed if // not in path from root to k path.push_back(root->key); // See if the k is same as root's key if (root->key == k) return true; // Check if k is found in left or right sub-tree if ( (root->left && findPath(root->left, path, k)) || (root->right && findPath(root->right, path, k)) ) return true; // If not present in subtree rooted with root, remove root from // path[] and return false path.pop_back(); return false;}// Returns LCA if node n1, n2 are present in the given binary tree,// otherwise return -1int findLCA(Node *root, int n1, int n2){ // to store paths to n1 and n2 from the root vector<int> path1, path2; // Find paths from root to n1 and root to n1. If either n1 or n2 // is not present, return -1 if ( !findPath(root, path1, n1) || !findPath(root, path2, n2)) return -1; /* Compare the paths to get the first different value */ int i; for (i = 0; i < path1.size() && i < path2.size() ; i++) if (path1[i] != path2[i]) break; return path1[i-1];}A Bottom-up Approach (Worst case O(n) ): Post-Order Traversal
We traverse from the bottom, and once we reach a node which matches one of the two nodes, we pass it up to its parent. The parent would then test its left and right subtree if each contain one of the two nodes. If yes, then the parent must be the LCA and we pass its parent up to the root. If not, we pass the lower node which contains either one of the two nodes (if the left or right subtree contains either p or q), or NULL (if both the left and right subtree does not contain either p or q) up.
题解的分析漏掉了一种情况，即树中可能只含有 A/B 中的一个节点！这种情况应该返回空值，但上述实现均返回非空节点
Node *LCA(Node *root, Node *p, Node *q) {
题解的分析漏掉了一种情况，即树中可能只含有 A/B 中的一个节点！这种情况应该返回空值，但上述实现均返回非空节点
Node *LCA(Node *root, Node *p, Node *q) {
if (!root) return NULL;
if (root == p || root == q) return root;
Node *L = LCA(root->left, p, q);
Node *R = LCA(root->right, p, q);
if (L && R) return root; // if p and q are on both sides
return L ? L : R; // either one of p,q is on one side OR p,q is not in L&R subtrees
}
// This function returns pointer to LCA of two given values n1 and n2.// v1 is set as true by this function if n1 is found// v2 is set as true by this function if n2 is foundstruct Node *findLCAUtil(struct Node* root, int n1, int n2, bool &v1, bool &v2){ // Base case if (root == NULL) return NULL; // If either n1 or n2 matches with root's key, report the presence // by setting v1 or v2 as true and return root (Note that if a key // is ancestor of other, then the ancestor key becomes LCA) if (root->key == n1) { v1 = true; return root; } if (root->key == n2) { v2 = true; return root; } // Look for keys in left and right subtrees Node *left_lca = findLCAUtil(root->left, n1, n2, v1, v2); Node *right_lca = findLCAUtil(root->right, n1, n2, v1, v2); // If both of the above calls return Non-NULL, then one key // is present in once subtree and other is present in other, // So this node is the LCA if (left_lca && right_lca) return root; // Otherwise check if left subtree or right subtree is LCA return (left_lca != NULL)? left_lca: right_lca;}
// Returns true if key k is present in tree rooted with root
bool find(Node *root, int k){ // Base Case if (root == NULL) return false; // If key is present at root, or in left subtree or right subtree, // return true; if (root->key == k || find(root->left, k) || find(root->right, k)) return true; // Else return false return false;}// This function returns LCA of n1 and n2 only if both n1 and n2 are present// in tree, otherwise returns NULL;Node *findLCA(Node *root, int n1, int n2){ // Initialize n1 and n2 as not visited bool v1 = false, v2 = false; // Find lca of n1 and n2 using the technique discussed above Node *lca = findLCAUtil(root, n1, n2, v1, v2); // Return LCA only if both n1 and n2 are present in tree if (v1 && v2 || v1 && find(lca, n2) || v2 && find(lca, n1)) return lca; // Else return NULL return NULL;}
// Return #nodes that matches P or Q in the subtree.
int countMatchesPQ(Node *root, Node *p, Node *q) {
if (!root) return 0;
int matches = countMatchesPQ(root->left, p, q) + countMatchesPQ(root->right, p, q);
if (root == p || root == q)
return 1 + matches;
else
return matches;
}
Node *LCA(Node *root, Node *p, Node *q) {
if (!root || !p || !q) return NULL;
if (root == p || root == q) return root;
int totalMatches = countMatchesPQ(root->left, p, q);
if (totalMatches == 1)
return root;
else if (totalMatches == 2)
return LCA(root->left, p, q);
else /* totalMatches == 0 */
return LCA(root->right, p, q);
http://wp.javayu.me/2014/02/lowest-common-ancestor-of-a-binary-tree/
在访问到leaf后结果按照bottom-up的方式向上传递。之前top-down approach是每次都检查两边的子树，然后进入一棵，再检查其子树，重复的部分在于：子树可能被多次check。而通过bottom-up的方式，信息流只需要一次就能到位.
算法优化，如果有多次重复问题的情况下，找出每次重复之间的重复子问题关系，寻找合适的信息流向让计算更快捷
树的recursive算法不一定要先判断当前节点再判断子树，如果子树的信息对于当前节点有用，则可以颠倒顺序变成bottom-up的方式
树的bottom-up方式和top-down方式的主要差别就在于：先处理当前节点还是先处理子树
recursion时，返回的值不一定要是最终的是否判断。也可以返回其他包含信息量更多的内容。
http://www.code123.cc/docs/leetcode-notes/binary_tree/lowest_common_ancestor.html
自底向上(计数器)
我们可以对返回结果添加计数器来解决。
定义pair result(node, counter)表示遍历到某节点时的返回结果，返回的node表示LCA 路 径中的可能的最小节点，相应的计数器counter则表示目前和A或者B匹配的节点数，若计数器为2，则表示已匹配过两次，该节点即为所求，若只匹配过一 次，还需进一步向上递推。表述地可能比较模糊，还是看看代码吧。
TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *A, TreeNode *B) {
if ((NULL == A) || (NULL == B)) return NULL;
pair result = helper(root, A, B);
if (A != B) {
return (2 == result.second) ? result.first : NULL;
} else {
return (1 == result.second) ? result.first : NULL;
}
}
pair helper(TreeNode *root, TreeNode *A, TreeNode *B) {
TreeNode * node = NULL;
if (NULL == root) return make_pair(node, 0);
pair left = helper(root->left, A, B);
pair right = helper(root->right, A, B);
// return either A or B
int count = max(left.second, right.second);
if (A == root || B == root) return make_pair(root, ++count);
// A and B are on both sides
if (NULL != left.first && NULL != right.first) return make_pair(root, 2);
// return either left or right or NULL
return (NULL != left.first) ? left : right;
}
This algorithm runs in O(n) time on a balanced tree. This is because c overs is called on 2n nodes in the first call (n nodes for the left side, and n nodes for the right side). After that the algorithm branches left or right, at which point c overs will be called on 2rz nodes, then 2X, and so on. This results in a runtime ofO(n).
TreeNode commonAncestor(TreeNode root, TreeNode p, TreeNode q) {/* Error check - one node is not in the tree. */
if (!covers(root, p) || !covers(root, q)) {
return null;
}
return ancestorHelper(root, p, q);
}
TreeNode ancestorHelper(TreeNode root, TreeNode p, TreeNode q) {
if (root== null || root== p || root== q) {
return root;
}
boolean plsOnleft = covers(root.left, p);
boolean qlsOnLeft = covers(root.left, q);
if (plsOnLeft != qlsOnLeft) {//Nodes are on different side
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);
}
there is still some inefficiency in how it operates. Specifically, covers searches all nodes under root for p and q, including the nodes in each subtree (root. left and root. right). Then, it picks one of those subtrees and searches all of its nodes. Each subtree is searched over and over again.
class Result {
public TreeNode node;
public boolean isAncestor;
public Result(TreeNode n, boolean isAnc) {
node = n;
isAncestor = isAnc;
}
}
TreeNode commonAncestor(TreeNode root, TreeNode p, TreeNode q) {
Result r = commonAncestorHelper(root, p, q);
if (r.isAncestor) {
return r.node;
}
return null;
}
Result commonAncHelper(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) return new Result(null, false);
if (root==p && root== q) {
return new Result(root, true);
}
Result rx = commonAncHelper(root.left, p, q);
if (rx.isAncestor) {//Found common ancestor
return rx;
}
Result ry = commonAncHelper(root.right, p, q);
if (ry.isAncestor) {//Found common ancestor
return ry;
}
if (rx.node != null && ry.node != null) {
return new Result(root, true); // This is the common ancestor
} else if (root == p || root == q) {
/* If we're currently at p or q, and we also found one of those nodes in a
* subtree, then this is truly an ancestor and the flag should be true. */
boolean isAncestor = rx.node != null I I ry.node != null;
return new Result(root, isAncestor);
} else {
return
new Result(rx.node!=null ? rx.node ry.node, false);
}
}
Of course, as this issue only comes up when p or q is not actually in the tree, an alternative solution would be to first search through the entire tree to make sure that both nodes exist.
/* The below code has a bug.*/TreeNode commonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root null) return null;
if (root == p && root == q) return root;
TreeNode x = commonAncestor(root.left, p, q);
if (x != null && x != p && x != q) {
// Already found ancestor
return x;
}
TreeNode y = commonAncestor(root.right, p, q);
if (y != null && y != p && y != q) { // Already found ancestor
return y;
}
if (x != null && y != null) { // p and q found in diff.subtrees
return root; II This is the common ancestor
} else if (root == p I I root == q) {
return root;
} else {
return x == null ? y x; I* return the non-null value *I
}
}
https://www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor/
http://blog.csdn.net/fightforyourdream/article/details/20441629
http://www.fusu.us/2013/06/p2-lowest-common-ancestor-in-binary-tree.html
https://github.com/mintycc/OnlineJudge-Solutions/blob/master/Leetcode/236_Lowest_Common_Ancestor_of_a_Binary_Tree.java
public void findFather(TreeNode root, Map<TreeNode, TreeNode> father) {
if (root.left != null) {
father.put(root.left, root);
findFather(root.left, father);
}
if (root.right != null) {
father.put(root.right, root);
findFather(root.right, father);
}
}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) return null;
if (p == null) return null;
if (q == null) return null;
Map<TreeNode, TreeNode> father = new HashMap<TreeNode, TreeNode>();
findFather(root, father);
int pdep = 0, qdep = 0;
for (TreeNode tmp = p; tmp != root; tmp = father.get(tmp)) pdep ++;
for (TreeNode tmp = q; tmp != root; tmp = father.get(tmp)) qdep ++;
while (pdep > qdep) {
p = father.get(p);
pdep --;
}
while (pdep < qdep) {
q = father.get(q);
qdep --;
}
while (p != q) {
p = father.get(p);
q = father.get(q);
}
return p;
}
Map<TreeNode, TreeNode> father = new HashMap<TreeNode, TreeNode>();
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) return null;
traverse(root);
Set<TreeNode> visited = new HashSet<TreeNode>();
for (TreeNode tmp = p; tmp != null; tmp = father.getOrDefault(tmp, null))
visited.add(tmp);
for (TreeNode tmp = q; tmp != null; tmp = father.getOrDefault(tmp, null))
if (visited.contains(tmp)) return tmp;
return null;
}
private void traverse(TreeNode root) {
if (root.left != null) {
father.put(root.left, root);
traverse(root.left);
}
if (root.right != null) {
father.put(root.right, root);
traverse(root.right);
}
}
此题还有一种情况，题目中没有明确说明p和q是否是树中的节点，如果不是，应该返回NULL，而上面的方法就不正确了，对于这种情况请参见 Cracking the Coding Interview 5th Edition 的第233-234页
X. Follow up // One TreeNode maybe not in the tree TreeNode single = new TreeNode(Integer.MAX_VALUE);
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
TreeNode rtn = lca(root, p, q);
if (rtn == null || rtn == single) return null;
return rtn;
}
public TreeNode lca(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) return null;
TreeNode tl = lca(root.left, p, q);
TreeNode tr = lca(root.right, p, q);
if (root == p || root == q) {
if (tl != null || tr != null) return root;
return single;
}
return tl == null ? tr : (tr == null ? tl : root);
}
General Tree
public class TreeNode {
int val;
TreeNode[] children;
TreeNode(int x, int n) {
val = x;
children = new TreeNode[n];
}
}
public TreeNode LCA(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) return root;
int count = 0;
TreeNode last = null;
for (TreeNode child : root.children) {
TreeNode tmp = LCA(child, p, q);
if (tmp != null) {
count ++;
last = tmp;
}
}
if (count == 0) return null;
if (count == 1) return last;
return root;
}
2. General Tree，⾮非
⼆二叉 (code)
3. Parent node + Set: O(h) (code)
4. Path + BinarySearch O(n^2 + klogn)
5. Doubling Algorithm O(nlogn + klogn) 过 难了了
6. Tarjan 吹⽜牛逼
1. 如果每个node包含parent指针 (向上parent直到root，⽤用set找重复路路径)
2. 假设node的值不不重复，但node没有parent pointer。给出了了O(n)的解，
n是binary tree中node的数量量。(a.HashMap储存parent关系 b.遍历binary
tree，找出2个node到root的path然后⽐比较 c. O(n^2)预处理理找出所有path
或者O(nlogn)倍增，然后BinarySearch找相同前缀)
3. follow up 是如果有⼀一个treenode 不不在树⾥里里应该怎么做 (helper函数
+Single返回值);之后的follow up是设计⼀一个存储结构，使得搜索只需要
O(lg(n))时间 (a.O(n^2)预处理理找出所有path然后BinarySearch b.O(nlogn)
倍增);
4. 找⼀一个general树的LCA
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/discuss/187535/Python-
My solution is the standard DFS with a flag, if we found the LCA in the left tree return directly.
The flag I used is like suming subtree to a value, If we find v1 or v2 in left tree then it gets a value of 1, if we find the value at current node, it gets 1. Then we check if value of left tree is larger than 2 then LCA must be there, other wise if its value is 1, then it has one of the target nodes. Same for right subtree and current node.
The flag I used is like suming subtree to a value, If we find v1 or v2 in left tree then it gets a value of 1, if we find the value at current node, it gets 1. Then we check if value of left tree is larger than 2 then LCA must be there, other wise if its value is 1, then it has one of the target nodes. Same for right subtree and current node.
