【二叉搜索树的最近公共祖先】【二叉搜索树性质】Leetcode 235. 二叉搜索树的最近公共祖先
- 【巧】解法1 利用二叉搜索树有序的性质
- 解法2 采用二叉树求最近公共祖先的方法——后序遍历
---------------🎈🎈235. 二叉搜索树的最近公共祖先 题目链接🎈🎈-------------------
【巧】解法1 利用二叉搜索树有序的性质
二叉搜索树的特点被应用
如果root大于p和q,说明p和q的最近公共祖先一定在当前节点的左子树中, 那么就只需要向左遍历
如果root小于p和q ,说明p和q的最近公共祖先一定在当前节点的右子树中, 那么就只需要向右遍历
如果root的值介于p和q之间,说明root一定是p和q的公共祖先,这时候返回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.val > p.val && root.val > q.val){ // 如果root大于p和q 那么就只需要向左遍历 结果不断return上去
return lowestCommonAncestor(root.left,p,q);
}
if(root.val < p.val && root.val < q.val){ // 如果root小于p和q 那么就只需要向右遍历 结果不断return上去
return lowestCommonAncestor(root.right,p,q);
}
// 如果等于或者root的值介于p和q之间,这时候返回root即可
return root;
}
}
解法2 采用二叉树求最近公共祖先的方法——后序遍历
/**
* 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) return null;
if(root==p ||root==q) return root;
TreeNode left = lowestCommonAncestor(root.left,p,q);
TreeNode right = lowestCommonAncestor(root.right,p,q);
if(left == null && right==null) return null;
else if(left == null && right!=null) return right;
else if(left != null && right==null) return left;
else return root;
}
}