---------------🎈🎈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;}
}