Lowest Common Ancestor triple punch.
basic problem
- Lintcode poke me (follow up)
- Leetcode poking me
The title
Description
Given the root and two nodes in a Binary Tree. Find the lowest common ancestor(LCA) of the two nodes.
The lowest common ancestor is the node with largest depth which is the ancestor of both nodes.
Notice:
Assume two nodes are exist in tree.
Example
For the following binary tree:
4
/ \
3 7
/ \
5 6
Copy the code- LCA(3, 5) = 4
- LCA(5, 6) = 7
- LCA(6, 7) = 7
Tags
LinkedIn LintCode Copyright Binary Tree Facebook
Analysis of the
Direct recursive traversal of path on Leetcode would explode the stack. O(1) = O(1) = O(1) = O(1)
At the spatial complexity of O(1), the idea is quite strange, and the monkey takes a while to figure out the solution.
First, Given the root and two nodes ina Binary Tree, the Given two nodes must be in the Tree, which is very important and supports the core idea of the solution:
- To solve LCA is to solve the Most Possible LCA
Let’s look at the code with comments.
Maybe I’m a little dull. I think this is a basic problem for follow up.
The complete code
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(intx) { val = x; }}// Two nodes are in the tree
public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) {
return null;
}
// p and q must exist in tree, so that lca of p and q must exist
return findMostPossibleLCA(root, p, q);
}
private TreeNode findMostPossibleLCA(TreeNode root, TreeNode node1, TreeNode node2) {
if (root == null) {
return null;
}
if (root == node1 || root == node2) {
return root;
}
TreeNode leftPLCA = findMostPossibleLCA(root.left, node1, node2);
TreeNode rightPLCA = lowestCommonAncestor(root.right, node1, node2);
if (leftPLCA == null && rightPLCA == null) {
// must not exist LCA
return null;
}
if(leftPLCA ! =null&& rightPLCA ! =null) {
// must be LCA
return root;
}
// most possible be LCA
returnleftPLCA ! =null? leftPLCA : rightPLCA; }}Copy the codefollow up 1
- Lintcode poking me
The title
Description
Given the root and two nodes in a Binary Tree. Find the lowest common ancestor(LCA) of the two nodes.
The lowest common ancestor is the node with largest depth which is the ancestor of both nodes.
The node has an extra attribute parent which point to the father of itself. The root’s parent is null.
Notice:
Assume two nodes are exist in tree.
Example
For the following binary tree:
4
/ \
3 7
/ \
5 6
Copy the code- LCA(3, 5) = 4
- LCA(5, 6) = 7
- LCA(6, 7) = 7
Tags
LintCode Copyright Binary Tree
Analysis of the
The two nodes are still in the tree, with the parent pointer added.
With the parent pointer, the time complexity can be reduced to O(LGN) and the space complexity to O(1).
The length difference synchronization technique in linked list problem is used.
The complete code
class ParentTreeNode {
public ParentTreeNode parent, left, right;
}
public class FollowUp1 {
// 1. Walk up to root to get two depths d1 and d2
// 2. Go back to the node and take abs(D1-d2) steps further
// 3. Then go min(d1,d2) together. There must be a root node in the process
// Time (LGN), space (1)
public ParentTreeNode lowestCommonAncestor(ParentTreeNode root, ParentTreeNode p, ParentTreeNode q) {
ParentTreeNode node1 = p;
ParentTreeNode node2 = q;
if (root == null || node1 == null || node2 == null) {
return null;
}
int depth1 = getDepth(root, node1);
int depth2 = getDepth(root, node2);
if (depth1 == -1 || depth2 == -1) {
return null;
}
ParentTreeNode startNode1 = node1;
ParentTreeNode startNode2 = node2;
int depth = depth1;
if (depth1 > depth2) {
for (int i = 0; i < depth1 - depth2; i++) {
startNode1 = startNode1.parent;
}
depth = depth2;
} else if (depth1 < depth2) {
for (int i = 0; i < depth2 - depth1; i++) {
startNode2 = startNode2.parent;
}
depth = depth1;
}
for (int i = 0; i < depth; i++) {
if (startNode1 == startNode2) {
return startNode1;
}
startNode1 = startNode1.parent;
startNode2 = startNode2.parent;
}
throw new RuntimeException("UnknownError");
}
private int getDepth(ParentTreeNode root, ParentTreeNode target) {
int depth = 1;
ParentTreeNode node = target;
for(; node.parent ! =null; node = node.parent) {
if (node == root) {
break;
}
depth++;
}
if (node == root) {
return depth;
}
return -1; }}Copy the codefollow up 2
- Lintcode poking me
The title
Description
Given the root and two nodes in a Binary Tree. Find the lowest common ancestor(LCA) of the two nodes.
The lowest common ancestor is the node with largest depth which is the ancestor of both nodes.
Return null if LCA does not exist.
Notice:
node A or node B may not exist in tree.
Example
For the following binary tree:
4
/ \
3 7
/ \
5 6
Copy the code- LCA(3, 5) = 4
- LCA(5, 6) = 7
- LCA(6, 7) = 7
Tags
LinkedIn LintCode Copyright Binary Tree Facebook
Analysis of the
The two nodes may not be in the tree, and the node does not have a parent pointer.
Since there is no parent pointer, the tree traverses to find a node with at least O(n) time complexity. At the same time, it takes O(n) space complexity to record paths.
The complete code
public class FollowUp2 {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
TreeNode node1 = p;
TreeNode node2 = q;
if (root == null || node1 == null || node2 == null) {
return null;
}
Stack<TreeNode> path1 = new Stack<>();
if(! dfsPreorder(root, node1, path1)) {return null;
}
Stack<TreeNode> path2 = new Stack<>();
if(! dfsPreorder(root, node2, path2)) {return null;
}
TreeNode lca = null;
for (int i = 0; i < path1.size() && i < path2.size(); i++) {
if(path1.get(i) ! = path2.get(i)) {break;
}
lca = path1.get(i);
}
return lca;
}
private boolean dfsPreorder(TreeNode root, TreeNode node, Stack<TreeNode> path) {
path.push(root);
if (root == node) {
return true;
}
if(root.left ! =null && dfsPreorder(root.left, node, path)) {
return true;
}
if(root.right ! =null && dfsPreorder(root.right, node, path)) {
return true;
}
path.pop();
return false; }}Copy the codeLinks to this article:
【 答 案 】 : Monkey at Lowest Common Ancestor Monkeysayhi.github. IO This article is published under the Creative Commons Attribution – Share Alike 4.0 International License. You are welcome to republish, reproduce, or use it for commercial purposes.