非递归-二叉搜索树的最近公共祖先

在这里插入图片描述

求解代码

如果根节点的值和p,q的差值相乘是正数，说明这两个差值要么都是正数，要么都是负数，所以p、q肯定位于根节点的同一侧，需要继续往下找；

如果相乘的结果是负数，说明p、q位于根节点的值两侧；

如果相乘为0，说明p，q至少有一个是根节点的值。

1
2
3
4
5
6
7


public int lowestCommonAncestor (TreeNode root, int p, int q) {
        
        while ((root.val-p)*(root.val-q)>0) {
            root = root.val>p?root.left:root.right;
        }
        return root.val;
    }