LeetCode 235. 二叉搜索树的最近公共祖先 (递归)

思路

利用二叉搜索树的性质，左子树中的值都小于根节点，右子树中的值都大于根节点；

1. 根据题意要找到公共父节点，也就是说，p和q在一个节点的两端，即一个大于根节点，一个小于根节点
2. 所以可以使用递归的方式，如果p和q同时小于或者大于根节点，就去他的对应的左子树(同时小于都在左子树中)和右子树(同时大于都在右子树中)中寻找。
3. 直到找到不同时大于或者小于的根节点，就是他们的最近公共父节点(第一次遇到这样的节点，一定是最近的)

代码实现

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/class Solution {TreeNode res = null;public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {res = root;// 如果两个节点，不能同时大于或同时小于一个节点，那么这个节点就是他们的最近公共祖先if(root.val < p.val && root.val < q.val) res = lowestCommonAncestor(root.right, p, q);if(root.val > p.val && root.val > q.val) res = lowestCommonAncestor(root.left, p, q);return res;}
}