题目描述

本题选自 LeetCode 98. 验证二叉搜索树

题目描述

给定一个二叉树，判断其是否是一个有效的二叉搜索树。 假设一个二叉搜索树具有如下特征：

• 节点的左子树只包含小于当前节点的数。
• 节点的右子树只包含大于当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

示例 1:

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

示例 2:

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

解题思路

一棵二叉搜索树，任意节点的左子树小于其根节点，任意节点的右子树大于其根节点。

第一种解法： 因为中序遍历是以 左-中-右 的顺序遍历的，因此，验证是否是二叉搜索树，我们可以通过验证中序遍历的结果是否是升序的来解决。

第二种解法： 因为在第一种解法中，我们需要额外申请一个数组空间进行存储，但实际上，每次验证我们只需要比较每个节点的有效性。因此，我们可以将中序遍历的过程进行拆解，在递归的过程中加入节点比较。

题解

• 递归解法1（额外的数组空间）

var isValidBST = function (root) {
    let arr = [];
    traverse(root);
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] <= arr[i - 1]) return false;
    }
    return true;
    function traverse(node) {
        if (!node) return;
        traverse(node.left);
        arr.push(node.val);
        traverse(node.right);
    }
};

• 递归解法2（使用最大、最小的临时变量）

var isValidBST = function (root) {
    return isValid(root);
    function isValid(node, min, max) {
        if (!node) return true;
        if (min !== undefined && node.val <= min) return false;
        if (max !== undefined && node.val >= max) return false;
        // 对于左子树，最大的值不能大于 node.val
        // 对于右子树，最小的值不能小于 node.val
        return isValid(node.left, min, node.val) && isValid(node.right, node.val, max);
    }
};

• 递归解法3（使用一个临时变量，最佳实践）

var isValidBST = function (root) {
    let num;
    return isValid(root);
    function isValid(node) {
        if (!node) return true;
        let right = isValid(node.left);
        if (!right || num !== undefined && num >= node.val) return false;
        // 保存前一个值用于升序比较
        num = node.val;
        return isValid(node.right);
    }
};

• 中序遍历的迭代解法

var isValidBST = function (root) {
    let num;
    let nodes = [];
    let node = root;
    while (node || nodes.length) {
        if (node) {
            nodes.push(node);
            node = node.left;
        } else {
            node = nodes.pop();
            if (num !== undefined && num >= node.val) return false;
            num = node.val;
            node = node.right;
        }
    }
    return true;
};

总结

递归是一种很优美的解法，复杂的题目往往也只需要简洁的代码。递归和迭代是解题过程中可以互相转化的两种解题思路，可以在具体情况下选择其中更优的解法。

前期回顾

Leetcode303 区域和检索 | 刷题打卡

LeetCode 组合总和三连 | 刷题打卡

LeetCode 703 数据流中的第 K 大元素 | 刷题打卡

LeetCode 239 滑动窗口最大值 | 刷题打卡

LeetCode 242 有效的字母异位词 | 刷题打卡

LeetCode 15 三数之和 | 刷题打卡