验证二叉搜索树

题目描述

力扣链接🔗

代码分析

数组法

大体思路为：将根据中序遍历将二叉搜索树的所有节点遍历在集合中，再判断集合是否递增即可。但数组法的时间复杂度为O(n ^ n)。

/**
 * 解法一：中序遍历获得一个数组，判断数组是否升序
 *
 * @param root
 * @return
 */
List<Integer> res = new ArrayList<>();
public boolean isValidBST(TreeNode root) {
    traversal(root);
    // 对集合进行判断
    for (int i = 1; i < res.size(); i++) {
        if (res.get(i) <= res.get(i - 1)) {   // 二叉搜索树不能相等
            return false;
        }
    }
    return true;
}
public TreeNode traversal(TreeNode root) {
    if (root == null) {
        return null;
    }
    if (root.left != null) traversal(root.left);
    res.add(root.val);
    if (root.right != null) traversal(root.right);
    return root;
}

递归法

大坑：不能单纯的判断左边小于中间，右边大于中间，搜索二叉树是左边所有节点小于中间节点，右边所有节点大于中间节点。

例如：

if (root->val > root->left->val && root->val < root->right->val) {
    return true;
} else {
    return false;
}

以上就是错误代码，无法解决这种情况。

还有一个坑，样例中最小节点 可能是int的最小值，如果这样使用最小的int来比较也是不行的。所以优化后将最左边的值存到变量中，此时就没有比最左边的值更小的值。

1. 确定返回值和参数
   由于时返回当前是否为二叉搜索树，所以不需要全部遍历，所以返回值为boolean
2. 终止递归条件
   由于搜索二叉树可以为空，所以为空时返回true
3. 处理每层的逻辑
   中序遍历，一直更新maxVal，一旦发现maxVal >= root->val，就返回false，注意元素相同时候也要返回false。

  /**
     * 递归法
     *
     * @param root
     * @return
     */
    TreeNode pre = null;  // 用来记录前一个节点的值，注意需要设置为null，不能new，会默认将val设置为0，此时0的情况会判断为false
    public boolean isValidBST(TreeNode root) {
        if (root == null) { // 当为空时也为二叉搜索树
            return true;
        }
        boolean left = isValidBST(root.left);// 左
        if (pre != null && pre.val >= root.val) return false; // 右
        pre = root; // 获取上一个节点
        boolean right = isValidBST(root.right);// 右
        return left && right;   // 判断左右是否为二叉搜索树
    }
}

迭代法

迭代法的思路：还是利用了中序遍历的思路，再中间处理一下节点即可，判断方法和递归一致。

/**
 * 迭代法（中序）
 *
 * @param root
 * @return
 */
public boolean isValidBST(TreeNode root) {
    TreeNode pre = null;    // 用来记录前一个节点
    TreeNode cur = root;    // 用来记录前一个节点
    Stack<TreeNode> stack = new Stack<>();
    while (cur != null || !stack.isEmpty()) {
        if (cur != null) {
            stack.push(cur);
            cur = cur.left; // 一直将左孩子入栈
        } else {
            cur = stack.pop();// 左孩子为空时
            if (pre != null && pre.val >= cur.val) return false;
            pre = cur;
            cur = cur.right;
        }
    }
    return true;
}