算法|【leetcode刷题】[简单]235. 二叉搜索树的最近公共祖先（lowest common ancestor of a binary search tree)-java
二叉搜索树的最近公共祖先 lowest common ancestor of a binary search tree
- 题目
- 分析
- 解答
题目 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
![算法|【leetcode刷题】[简单]235. 二叉搜索树的最近公共祖先（lowest common ancestor of a binary search tree)-java](https://img.it610.com/image/info8/1a7fa5e434e6497c9a1f9ec269526fc7.jpg)
文章图片
示例 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 为不同节点且均存在于给定的二叉搜索树中。
/**
* 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 p, TreeNode q) {}
}分析 【算法|【leetcode刷题】[简单]235. 二叉搜索树的最近公共祖先（lowest common ancestor of a binary search tree)-java】首先p和q都分布在左数的话，也就是p,q的值都比root的左树少；右树也是这个原理。其余的直接返回root。
解答
/**
* 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 p, TreeNode q) {
if(root == null || root == p || root == q){
return root;
}
if(root.val > p.val && root.val > q.val ){
return lowestCommonAncestor(root.left,p,q);
}
else if(root.val 推荐阅读
- 宽容谁
- 我要做大厨
- 增长黑客的海盗法则
- 画画吗（）
- 2019-02-13——今天谈梦想（）
- 远去的风筝
- 三十年后的广场舞大爷
- 叙述作文
- 20190302|20190302 复盘翻盘
- 学无止境，人生还很长