题目链接

普通递归法

/*** 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 || p == root || q == root){return root;}TreeNode left = lowestCommonAncestor(root.left, p, q);TreeNode right = lowestCommonAncestor(root.right, p, q);if(left != null && right != null){return root;}if(left == null){return right;}return left;}
}

利用二叉搜索树特性递归

/*** 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){return lowestCommonAncestor(root.left, p, q);}else if(root.val < p.val && root.val < q.val){return lowestCommonAncestor(root.right, p, q);}else{return root;}}
}

二叉搜索树最近公共祖先比普通二叉树公共祖先问题简单，不用使用回溯，二叉树自带方向性，遇到目标区间的节点可以直接返回。