jd0405.合法二叉搜索树

题目描述

实现一个函数，检查一棵二叉树是否为二叉搜索树。

示例一：

输入:
    2
   / \
  1   3
输出: true

示例二：

输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ，但是其右子节点值为 4 。

题解

验证是否是二叉搜索树, 我们可以根据中序遍历结果是升序数组, 所以思路就是中序遍历这棵树, 一旦发现当前节点的数值小于等于前一个数, 那么就证明不是二叉搜索树.

简单来说, 就是在中序遍历的基础上创建一个变量记录着前一个数值, 多一个比较的步骤.

DFS 递归

long pre = Long.MIN_VALUE;

public boolean isValidBST(TreeNode root) {
    if (root == null)
        return true;

    if (!isValidBST(root.left))
        return false;

    if (root.val <= pre) {
        return false;
    }
    pre = root.val;

    return isValidBST(root.right);
}

---

DFS 迭代

public boolean isValidBST2(TreeNode root) {
    if (root == null)
        return true;
    long pre = Long.MIN_VALUE;
    Stack<TreeNode> stack = new Stack<>();
    TreeNode cur = root;

    while (cur != null || !stack.isEmpty()) {
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }

        cur = stack.pop();
        if (cur.val<=pre)
            return false;
        pre = cur.val;
        cur = cur.right;
    }
    return true;
}