共计 1029 个字符，预计需要花费 3 分钟才能阅读完成。
一、题目粗心
给定一个二叉搜寻树, 找到该树中两个指定节点的最近公共先人。
百度百科中最近公共先人的定义为：“对于有根树 T 的两个结点 p、q，最近公共先人示意为一个结点 x，满足 x 是 p、q 的先人且 x 的深度尽可能大（一个节点也能够是它本人的先人）。”
例如，给定如下二叉搜寻树: root = [6,2,8,0,4,7,9,null,null,3,5]
示例 1:
输出: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输入: 6
解释: 节点 2 和节点 8 的最近公共先人是 6。
示例 2:
输出: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输入: 2
解释: 节点 2 和节点 4 的最近公共先人是 2, 因为依据定义最近公共先人节点能够为节点自身。
阐明:
- 所有节点的值都是惟一的。
- p、q 为不同节点且均存在于给定的二叉搜寻树中。
起源：力扣（LeetCode）
链接：https://leetcode.cn/problems/…
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。
二、解题思路
求二叉树的最小独特父节点，能够用递归来求解，同志二叉搜寻树的特点是左 < 根 < 右，所以根节点的值始终都是两头值，大于左子树的所有节点值，小于右子树的所有节点值，咱们能够做如下判断，如果根节点的值大于 p 和 q 之间的较大值，阐明 q 和 q 都在左子树中，那么此时咱们就进入根节点的左子节点持续 uxjv，如果根节点小于 p 和 q 之间的较小值，阐明 p 和 q 都在右子树中，那么此时咱们就进入根节点的右子节点持续递归，如果都不是，则阐明以后根节点就是是近朱者赤; 近墨者黑独特父节点，间接返回即可。
三、解题办法
3.1 Java 实现
public class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if (root == null) {return root;}
if (root.val > Math.max(p.val, q.val)) {return lowestCommonAncestor(root.left, p, q);
} else if (root.val < Math.min(p.val, q.val)) {return lowestCommonAncestor(root.right, q, q);
} else {return root;}
}
}四、总结小记
- 2202/10/4 假期疫情瞬息万变