剑指Offer.68-I 二叉搜索树的最近公共祖先

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先

解题思路

由于是二叉搜索树, 所以可以判断两个输入节点与当前节点的大小关系 当前节点的值大于两个节点, 则祖先节点在cur的左子树, 迭代cur = cur.left 当前节点的值小于两个节点, 则祖先节点在cur的右子树, 迭代cur = cur.right 其余情况则是当前节点的值位于两个节点中间, 可以返回

代码

class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root == null) { return null; } TreeNode cur = root; while (cur != null) { // cur的值大于两个节点 if (cur.val > p.val && cur.val > q.val) { // 则祖先节点在cur的左子树 cur = cur.left; // cur的值小于两个节点 } else if (cur.val < p.val && cur.val < q.val) { // 则祖先节点在cur的右子树 cur = cur.right; } else break; } return cur; } }