Problem Description
level: medium
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.
Example
For the following binary tree:
|
1 2 3 4 5 6 7 |
4 / \ 3 7 / \ 5 6 |
LCA(3, 5) = 4
LCA(5, 6) = 7
LCA(6, 7) = 7
Consideration:
1. tradition method
2. divide & conquer algorithm
Approach 1:
Put the parent of the nodes into the two lists, then scan the lists from the bottom, to find the lower common one
For example: LCA(5,6)
List 1: 5,7,4
List 2: 6,7,4
comparing the lists from bottom, 4, 7 are common parents, and 7 is the closest
Another example: LCA(3, 5)
list 1: 3,4
list 2: 5,7,4
comparing the lists from bottom, 4 is common parent, and the closest
Approach 2:
Divide & conquer
psuedo code:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
get_ancestor(root, node1, node2) begin if(root == null || root == node1 || root == node2) { retuen root; } // divide node left = get_ancestor(root.left, node1, node2) node right = get_ancestor(root.right, node1, node2) if(left != null && right != null) return root; if(left != null) return left; if(right != null) return right; return null; end |
