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 search tree: root = [3,5,1,6,2,0,8,null,null,7,4]
_______3______
/ \
___5__ ___1__
/ \ / \
6 _2 0 8
/ \
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 of nodes 5 and 1 is 3.
Example 2:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself
according to the LCA definition.
题意：
二叉树最近公共祖先
思路：
用自底向上(bottom-up)的思路，先看看是否能在root的左子树中找到p或q，再看看能否在右子树中找到，
- 如果两边都能找到，说明当前节点就是最近公共祖先
- 如果左边没找到，则说明
p和q都在右子树 - 如果右边没找到，则说明
p和q都在左子树
recursion
1. search for either of two nodes(node1, node2) whose lca starting from root
2. any of the node is found, return that node to its parent
3. any node gets a not null node from left side and a not null node from right side, it is lca. return that node to its parent
___5__ root 5
/ \ root.left / /return 6 root.right\ \ return 4
6 _2 6 find node1 2
/ \ root.left //return null \\ return 4
7 4 7 4 find 4
node1: 6 node2: 4
code
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode node1, TreeNode node2) {
// base
if (root == null || root == node1 || root == node2) {
return root;
}
// go into recursion on left side, passing same node1, node2
TreeNode left = lowestCommonAncestor(root.left, node1, node2);
TreeNode right = lowestCommonAncestor(root.right, node1, node2);
// left != null && right != null
if (left != null && right != null) {
return root; // such root is lca
}
// left!=null && right ==null
if (left != null) {
return left;
}
// right!=null && left == null
if (right!=null) {
return right;
}
// right ==null && left == null
return null;
}
}