题目
题解
法一：
按照递归的思维去想：
递归终止条件
递归
返回值
1 如果p、q都不在root为根节点的子树中，返回null
2 如果p、q其中之一在root为根节点的子树中，返回该节点
3 如果p、q都在root为根节点的子树子树中，返回root节点
代码逻辑：
1 如果是遍历到null/node1/node2 => 会返回对应节点：null/node1/node2。
遍历左右子树：
2 如果两个子树都含node1/node2（因为二叉树中无重复元素，所以肯定是一边含一种node）=> 会返回此时的根节点：root;
3 如果两个子树只有一个子树含node1/node2 => 会返回node1/node2；如果两个子树都不含node1/node2=> 会返回：null;
4 如果是最近公共祖先的上层节点，=>会将最近公共祖先节点返回：node1/node2 。(此种情况可与3的前半种情况合并为一个判断分支)
todo
更新别的方法
法一代码
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) {
return root;
}
TreeNode lNode = lowestCommonAncestor(root.left, p, q);
TreeNode rNode = lowestCommonAncestor(root.right, p, q);
if (lNode == null && rNode == null) {
return null;
}
if (lNode != null && rNode != null) {
return root;
}
return lNode != null ? lNode : rNode;
}
题目 235. 二叉搜索树的最近公共祖先
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
题解
迭代、递归均可。这里使用迭代。
root往下走，找到第一个节点值介于两个目标节点值中间的节点。
时间负责度O(n),空间O(1)
代码
/**
* 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) {
while(root!=null){
if(p.val<root.val&&q.val<root.val){
root=root.left;
}else if(p.val>root.val&&q.val>root.val){
root=root.right;
}else{
return root;
}
}
return null;
}
}
