Related: LeetCode 236 - Lowest Common Ancestor in a Binary Tree
LeetCode 235 - Lowest Common Ancestor of a Binary Search Tree (BST)
Lowest Common Ancestor in a Binary Tree | Set 1 | GeeksforGeeks
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/
https://leetcode.com/articles/lowest-common-ancestor-of-a-binary-tree/
X. http://buttercola.blogspot.com/2015/08/leetcode-lowest-common-ancestor-of.html
LeetCode 235 - Lowest Common Ancestor of a Binary Search Tree (BST)
Lowest Common Ancestor in a Binary Tree | Set 1 | GeeksforGeeks
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
Given the following binary tree: root = [3,5,1,6,2,0,8,null,null,7,4]
Example 1:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 Output: 3 Explanation: The LCA of nodes5
and1
is3.
X.
http://rainykat.blogspot.com/2017/01/leetcode-236-lowest-common-ancestor-of.html
recursion: The idea is to traverse the tree starting from root. If any of the given keys (n1 and n2) matches with root, then root is LCA (assuming that both keys are present). If root doesn’t match with any of the keys, we recur for left and right subtree. The node which has one key present in its left subtree and the other key present in right subtree is the LCA. If both keys lie in left subtree, then left subtree has LCA also, otherwise LCA lies in right subtree
recursion: The idea is to traverse the tree starting from root. If any of the given keys (n1 and n2) matches with root, then root is LCA (assuming that both keys are present). If root doesn’t match with any of the keys, we recur for left and right subtree. The node which has one key present in its left subtree and the other key present in right subtree is the LCA. If both keys lie in left subtree, then left subtree has LCA also, otherwise LCA lies in right subtree
这道求二叉树的最小共同父节点的题是之前那道 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 ? left : right;
}
上述代码可以进行优化一下,如果当前结点不为空,且既不是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;
}
此题还有一种情况,题目中没有明确说明p和q是否是树中的节点,如果不是,应该返回NULL,而上面的方法就不正确了,对于这种情况请参见 Cracking the Coding Interview 5th Edition 的第233-234页。
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { CounterNode n = helper(root, p, q); return n.node; } public CounterNode helper(TreeNode root, TreeNode p, TreeNode q){ if(root==null){ return new CounterNode(null, 0); } CounterNode left = helper(root.left, p, q); if(left.count==2){ return left; } CounterNode right = helper(root.right, p, q); if(right.count==2){ return right; } int c=left.count+right.count+(root==p?1:0)+(root==q?1:0); return new CounterNode(root, c); } } class CounterNode{ public int count; public TreeNode node; public CounterNode(TreeNode node, int count){ this.count=count; this.node=node; } |
X. Post Order traverse
cases: the relationship between current node and target nodes
cases: the relationship between current node and target nodes
The approach is pretty intuitive. Traverse the tree in a depth first manner. The moment you encounter either of the nodes
p
or q
, return some boolean flag. The flag helps to determine if we found the required nodes in any of the paths. The least common ancestor would then be the node for which both the subtree recursions return a True
flag. It can also be the node which itself is one of p
or q
and for which one of the subtree recursions returns a True
flag.
Let us look at the formal algorithm based on this idea.
Algorithm
- Start traversing the tree from the root node.
- If the current node itself is one of
p
orq
, we would mark a variablemid
asTrue
and continue the search for the other node in the left and right branches. - If either of the left or the right branch returns
True
, this means one of the two nodes was found below. - If at any point in the traversal, any two of the three flags
left
,right
ormid
becomeTrue
, this means we have found the lowest common ancestor for the nodesp
andq
.
private TreeNode ans;
public Solution() {
// Variable to store LCA node.
this.ans = null;
}
private boolean recurseTree(TreeNode currentNode, TreeNode p, TreeNode q) {
// If reached the end of a branch, return false.
if (currentNode == null) {
return false;
}
// Left Recursion. If left recursion returns true, set left = 1 else 0
int left = this.recurseTree(currentNode.left, p, q) ? 1 : 0;
// Right Recursion
int right = this.recurseTree(currentNode.right, p, q) ? 1 : 0;
// If the current node is one of p or q
int mid = (currentNode == p || currentNode == q) ? 1 : 0;
// If any two of the flags left, right or mid become True
if (mid + left + right >= 2) {
this.ans = currentNode;
}
// Return true if any one of the three bool values is True.
return (mid + left + right > 0);
}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// Traverse the tree
this.recurseTree(root, p, q);
return this.ans;
}
Approach 3: Iterative without parent pointers
// Three static flags to keep track of post-order traversal.
// Both left and right traversal pending for a node.
// Indicates the nodes children are yet to be traversed.
private static int BOTH_PENDING = 2;
// Left traversal done.
private static int LEFT_DONE = 1;
// Both left and right traversal done for a node.
// Indicates the node can be popped off the stack.
private static int BOTH_DONE = 0;
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
Stack<Pair<TreeNode, Integer>> stack = new Stack<Pair<TreeNode, Integer>>();
// Initialize the stack with the root node.
stack.push(new Pair<TreeNode, Integer>(root, Solution.BOTH_PENDING));
// This flag is set when either one of p or q is found.
boolean one_node_found = false;
// This is used to keep track of the LCA.
TreeNode LCA = null;
// Child node
TreeNode child_node = null;
// We do a post order traversal of the binary tree using stack
while (!stack.isEmpty()) {
Pair<TreeNode, Integer> top = stack.peek();
TreeNode parent_node = top.getKey();
int parent_state = top.getValue();
// If the parent_state is not equal to BOTH_DONE,
// this means the parent_node can't be popped off yet.
if (parent_state != Solution.BOTH_DONE) {
// If both child traversals are pending
if (parent_state == Solution.BOTH_PENDING) {
// Check if the current parent_node is either p or q.
if (parent_node == p || parent_node == q) {
// If one_node_found was set already, this means we have found
// both the nodes.
if (one_node_found) {
return LCA;
} else {
// Otherwise, set one_node_found to True,
// to mark one of p and q is found.
one_node_found = true;
// Save the current top element of stack as the LCA.
LCA = stack.peek().getKey();
}
}
// If both pending, traverse the left child first
child_node = parent_node.left;
} else {
// traverse right child
child_node = parent_node.right;
}
// Update the node state at the top of the stack
// Since we have visited one more child.
stack.pop();
stack.push(new Pair<TreeNode, Integer>(parent_node, parent_state - 1));
// Add the child node to the stack for traversal.
if (child_node != null) {
stack.push(new Pair<TreeNode, Integer>(child_node, Solution.BOTH_PENDING));
}
} else {
// If the parent_state of the node is both done,
// the top node could be popped off the stack.
// Update the LCA node to be the next top node.
if (LCA == stack.pop().getKey() && one_node_found) {
LCA = stack.peek().getKey();
}
}
}
return null;
}
Approach 2: Iterative using parent pointers
If we have parent pointers for each node we can traverse back from
p
and q
to get their ancestors. The first common node we get during this traversal would be the LCA node. We can save the parent pointers in a dictionary as we traverse the tree.- Start from the root node and traverse the tree.
- Until we find
p
andq
both, keep storing the parent pointers in a dictionary. - Once we have found both
p
andq
, we get all the ancestors forp
using the parent dictionary and add to a set calledancestors
. - Similarly, we traverse through ancestors for node
q
. If the ancestor is present in the ancestors set forp
, this means this is the first ancestor common betweenp
andq
(while traversing upwards) and hence this is the LCA node.
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// Stack for tree traversal
Deque<TreeNode> stack = new ArrayDeque<>();
// HashMap for parent pointers
Map<TreeNode, TreeNode> parent = new HashMap<>();
parent.put(root, null);
stack.push(root);
// Iterate until we find both the nodes p and q
while (!parent.containsKey(p) || !parent.containsKey(q)) {
TreeNode node = stack.pop();
// While traversing the tree, keep saving the parent pointers.
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);
}
}
// Ancestors set() for node p.
Set<TreeNode> ancestors = new HashSet<>();
// Process all ancestors for node p using parent pointers.
while (p != null) {
ancestors.add(p);
p = parent.get(p);
}
// The first ancestor of q which appears in
// p's ancestor set() is their lowest common ancestor.
while (!ancestors.contains(q))
q = parent.get(q);
return q;
}
What if there is a pointer to the parent?
Method 2: without using extra space
xMethod 1 (By Storing root to n1 and root to n2 paths):
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.
Method 2 (Using Single Traversal)
If any of the given keys (n1 and n2) matches with root, then root is LCA (assuming that both keys are present). If root doesn’t match with any of the keys, we recur for left and right subtree. The node which has one key present in its left subtree and the other key present in right subtree is the LCA. If both keys lie in left subtree, then left subtree has LCA also, otherwise LCA lies in right subtree.
Note that the above method assumes that keys are present in Binary Tree. If one key is present and other is absent, then it returns the present key as LCA (Ideally should have returned NULL).
We can extend this method to handle all cases by passing two boolean variables v1 and v2. v1 is set as true when n1 is present in tree and v2 is set as true if n2 is present in tree.
We will soon be discussing more solutions to this problem. Solutions considering the following.
1) If there are many LCA queries and we can take some extra preprocessing time to reduce the time taken to find LCA.
2) If parent pointer is given with every node.
http://www.geeksforgeeks.org/lowest-common-ancestor-in-a-binary-tree-set-2-using-parent-pointer/
A O(h) time and O(1) Extra Space Solution
Read full article from Lowest Common Ancestor in a Binary Tree | Set 1 | GeeksforGeeks
public
Node findLCA(Node root, Node p, Node q) {
if
(root ==
null
|| p ==
null
|| q ==
null
)
return
null
;
int
depth1 = getDepth(root, p);
int
depth2 = getDepth(root, q);
if
(depth1 > depth2) {
swap(depth1, depth2);
swap(p, q);
}
for
(
int
i =
0
; i < depth1 - depth2; i++) {
q = q.parent;
}
while
(p) {
if
(p == q)
return
p;
p = p.parent;
q = q.parent;
}
return
null
;
}
public
int
getDepth(Node root, Node n) {
if
(root ==
null
|| n ==
null
)
return
null
;
int
depth =
0
;
while
(root != n) {
depth++;
n = n.parent;
}
return
depth;
}
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.
bool
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 -1
int
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];
}
Method 2 (Using Single Traversal)
If any of the given keys (n1 and n2) matches with root, then root is LCA (assuming that both keys are present). If root doesn’t match with any of the keys, we recur for left and right subtree. The node which has one key present in its left subtree and the other key present in right subtree is the LCA. If both keys lie in left subtree, then left subtree has LCA also, otherwise LCA lies in right subtree.
// This function returns pointer to LCA of two given values n1 and n2.
// This function assumes that n1 and n2 are present in Binary Tree
struct
Node *findLCA(
struct
Node* root,
int
n1,
int
n2)
{
// Base case
if
(root == NULL)
return
NULL;
// If either n1 or n2 matches with root's key, report
// the presence by returning root (Note that if a key is
// ancestor of other, then the ancestor key becomes LCA
if
(root->key == n1 || root->key == n2)
return
root;
// Look for keys in left and right subtrees
Node *left_lca = findLCA(root->left, n1, n2);
Node *right_lca = findLCA(root->right, n1, n2);
// 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;
}
//Root of the Binary Tree
Node root;
Node findLCA(
int
n1,
int
n2)
{
return
findLCA(root, n1, n2);
}
// This function returns pointer to LCA of two given
// values n1 and n2. This function assumes that n1 and
// n2 are present in Binary Tree
Node findLCA(Node node,
int
n1,
int
n2)
{
// Base case
if
(node ==
null
)
return
null
;
// If either n1 or n2 matches with root's key, report
// the presence by returning root (Note that if a key is
// ancestor of other, then the ancestor key becomes LCA
if
(node.data == n1 || node.data == n2)
return
node;
// Look for keys in left and right subtrees
Node left_lca = findLCA(node.left, n1, n2);
Node right_lca = findLCA(node.right, n1, n2);
// 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!=
null
&& right_lca!=
null
)
return
node;
// Otherwise check if left subtree or right subtree is LCA
return
(left_lca !=
null
) ? left_lca : right_lca;
}
We can extend this method to handle all cases by passing two boolean variables v1 and v2. v1 is set as true when n1 is present in tree and v2 is set as true if n2 is present in tree.
// 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 found
struct
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;
}
// Root of the Binary Tree
Node root;
static
boolean
v1 =
false
, v2 =
false
;
// 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 found
Node findLCAUtil(Node node,
int
n1,
int
n2)
{
// Base case
if
(node ==
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
(node.data == n1)
{
v1 =
true
;
return
node;
}
if
(node.data == n2)
{
v2 =
true
;
return
node;
}
// Look for keys in left and right subtrees
Node left_lca = findLCAUtil(node.left, n1, n2);
Node right_lca = findLCAUtil(node.right, n1, n2);
// 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 !=
null
&& right_lca !=
null
)
return
node;
// Otherwise check if left subtree or right subtree is LCA
return
(left_lca !=
null
) ? left_lca : right_lca;
}
// Finds lca of n1 and n2 under the subtree rooted with 'node'
Node findLCA(
int
n1,
int
n2)
{
// Initialize n1 and n2 as not visited
v1 =
false
;
v2 =
false
;
// Find lca of n1 and n2 using the technique discussed above
Node lca = findLCAUtil(root, n1, n2);
// Return LCA only if both n1 and n2 are present in tree
if
(v1 && v2)
return
lca;
// Else return NULL
return
null
;
}
1) If there are many LCA queries and we can take some extra preprocessing time to reduce the time taken to find LCA.
2) If parent pointer is given with every node.
http://www.geeksforgeeks.org/lowest-common-ancestor-in-a-binary-tree-set-2-using-parent-pointer/
Node *LCA(Node *n1, Node *n2)
{
// Creata a map to store ancestors of n1
map <Node *,
bool
> ancestors;
// Insert n1 and all its ancestors in map
while
(n1 != NULL)
{
ancestors[n1] =
true
;
n1 = n1->parent;
}
// Check if n2 or any of its ancestors is in
// map.
while
(n2 != NULL)
{
if
(ancestors.find(n2) != ancestors.end())
return
n2;
n2 = n2->parent;
}
return
NULL;
}
A O(h) time and O(1) Extra Space Solution
- erse up using parent pointers of both nodes, the first common node in the path to root is lca.
The idea is to find depths of given nodes and move up the deeper node pointer by the difference between depths. Once both nodes reach same level, traverse them up and return the first common node.
// A utility function to find depth of a node
// (distance of it from root)
int
depth(Node *node)
{
int
d = -1;
while
(node)
{
++d;
node = node->parent;
}
return
d;
}
// To find LCA of nodes n1 and n2 in Binary Tree
Node *LCA(Node *n1, Node *n2)
{
// Find depths of two nodes and differences
int
d1 = depth(n1), d2 = depth(n2);
int
diff = d1 - d2;
// If n2 is deeper, swap n1 and n2
if
(diff < 0)
{
Node * temp = n1;
n1 = n2;
n2 = temp;
diff = -diff;
}
// Move n1 up until it reaches the same level as n2
while
(diff--)
n1 = n1->parent;
// Now n1 and n2 are at same levels
while
(n1 && n2)
{
if
(n1 == n2)
return
n1;
n1 = n1->parent;
n2 = n2->parent;
}
return
NULL;
}