巧【二叉搜索树的最近公共祖先】【二叉搜索树的性质】Leetcode 235. 二叉搜索树的最近公共祖先

本文主要是介绍巧【二叉搜索树的最近公共祖先】【二叉搜索树的性质】Leetcode 235. 二叉搜索树的最近公共祖先，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【二叉搜索树的最近公共祖先】【二叉搜索树性质】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;}
}