BM38. [在二叉树中找到两个节点的最近公共祖先]
https://www.nowcoder.com/exam/oj?tab=%E7%AE%97%E6%B3%95%E7%AF%87&topicId=295
BM38. 在二叉树中找到两个节点的最近公共祖先
根据题目直接上模板就可以了
public int lowestCommonAncestor (TreeNode root, int p, int q) {
int left = lowestCommonAncestor(root.left, p, q);
int right = lowestCommonAncestor(root.right, p, q);
}
然后看题目公共祖先的定义也就是从当前节点出发，在当前节点可以左子树可以找到一个点，在有子树可以找到一个点。节点本身可以视为自己的祖先。
比如5和1的最近公共祖先就是3
5和6的最近公共祖先就是5
7和0的最近公共祖先就是3
思考一下是不是我们从上到下遍历二叉树，如果当前节点等于两个子节点其中的一个那么这个节点就是最近公共祖先，因为另一个节点不是存在他的左子树就是存在他的右子树。所以我们继续左右子树找和目标节点1和目标节点2相等的点。那么接下来就有出现三种情况
- 目标1在左子树，目标2在有子树
- 目标1和2都在左子树
- 目标1和3都在有子树
- 因为肯定存在这样的两个点所以不会出现都不在的情况
其实我们可以将上面情况抽象为两大类
第一类是和当前节点有关系，所以判断和当前节点是否相等
第二类当前节点没有关系受到左右子树的结果影响
由于我们我们返回的是找到的其中的一个节点的值的位置，数据范围0<=节点值<=10000，所以我们可以将没有找到这个节点值返回-1
public int lowestCommonAncestor (TreeNode root, int p, int q) {
if(root == null)
return -1;
//找到了任意一个值就可以返回证明有值在这个子树
if (p == root.val || q == root.val) {
return root.val;
}
// 如果公共祖先在左侧，那么就输出左面的点即可
int left = lowestCommonAncestor(root.left, p, q);
int right = lowestCommonAncestor(root.right, p, q);
if(left > 0 && right == -1)
return left;
if(right > 0 && left == -1)
return right;
if(left > -1 && right > -1)
return root.val;
return -1;
}
复杂度分析：
- 时间复杂度：
，其中
为节点数，递归遍历二叉树每一个节点
- 空间复杂度：
查看6道真题和解析