题目:
思路:
看到二叉树的题目,首先要想到递归,因为大多数的二叉树题目都是可以通过递归来解决的,再看这是一个二叉搜索树,立马就想到二叉搜索树的特质,左子树上所有节点的值都小于根节点的值,右子树上所有节点的值都大于根节点的值,它的左右子树也分别为二叉搜索树.那我们怎么能利用这个性质呢?
可以分三种情况来分析问题:
p,q 都比 root 节点值小,所以 p,q 都在左子树.
p,q 都比 root 节点值大,所以 p,q 都在右子树.
p,q 一个比 root 节点值小,一个比 root 节点值大,也就是 p,q 分布在 root 节点的左右子树两边.或者 p,q 其中一个节点就是 root 节点,此时都应该直接返回 root.
代码:
分析完所有的情况后,代码就比较好写了.根据上面的思路,解题代码如下所示:
class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (p.val < root.val && q.val < root.val) return lowestCommonAncestor(root.left, p, q); if (p.val > root.val && q.val > root.val) return lowestCommonAncestor(root.right, p, q); return root; } }
提交结果:
