给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
image
示例 1:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
示例 2:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。
说明:
- 所有节点的值都是唯一的。
- p、q 为不同节点且均存在于给定的二叉树中。
本题有两种思考角度，一种是递归，一种是存储父节点，我先讲一下存储父节点，这个方法只要想到了就基本都能写出来，重点在于思维角度，因此不写代码。
我们可以用一个哈希表遍历所有节点，除了root根节点以外所有节点的父节点将其存储起来。
然后再用一个set存储p节点的父节点，一直遍历到root节点为止。
这时候set里都是p的祖先节点，我们再去遍历q的父节点，当我们遍历到一个q的父节点出现在了set里那就是答案了，由于我们的遍历是自底向上，因此第一个匹配的节点就一定是离两个节点最近的公共祖先。
思路是很清晰的，递归就稍微难一点了。
递归的思路是用一个布尔值来确定左子树或者右子树是否含有p、q，如果左子树含有p，那就用一个变量leftson来储存是true，否则就是false。
显然答案就是 当leftson && rightson的时候那就是答案，但是不要忘记一个节点也可以是它自己的祖先，因此还需要加个或 leftson && rightson || ((root.val == p.val || root.val == q.val) && (leftson || rightson)) 这样就对了，当本节点的值和p，q相同的时候那只要左子树或者右子树有任意p，q即可。 请注意这样做的依据是 说明当中的内容，所有节点的值都是唯一的。且p,q为不同节点。
当判断条件出来了，那就基本都完成了，当我们将答案判断出来后，该祖先节点会将p,q两个合二为一当做一个父节点的leftson 或者 rightson。因此，之后也就不会再有父节点去匹配成功了。这是本题的一个递归的奥妙所在。
本题递归的思路，我认为还是比较难想到的，代码如下:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
TreeNode ans;
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
dfs(root,p,q);
return ans;
}
public boolean dfs(TreeNode root, TreeNode p, TreeNode q){
if(root == null) return false;
boolean leftSon = dfs(root.left,p,q);
boolean rightSon = dfs(root.right,p,q);
if( (leftSon && rightSon) || (( root.val == p.val || root.val == q.val ) && ( leftSon || rightSon )))
ans = root;
return leftSon || rightSon || root.val == p.val || root.val == q.val;
}
}
网友评论