98.验证二叉搜索树.md

LeetCode 98.验证二叉搜索树

描述

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。

节点的右子树只包含大于当前节点的数。

所有左子树和右子树自身必须也是二叉搜索树。

示例 1:

输入:
    2
   / \
  1   3

输出: true

示例 2:

输入:
    5
   / \
  1   4
     / \
    3   6
输出: false

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

题解

题意理解：

节点的左子树只包含小于当前节点的数。

节点的右子树只包含大于当前节点的数。

1. 节点左子树下的所有节点包括其下的右子节点都要小于当前节点
2. 节点右子树下的所有节点包括其下的左子节点都要大于当前节点

错误示例1： [5,3,7,2,6]

输入：
    5
   / \
  3   7
 / \
2   6
输出：false

解释：其中左子树3下的右子节点6 大于根节点5

错误示例2： [5,3,6,null,null,4,7]

输入：
      5
     / \
    3   6
       / \
      4   7
输出：false

解释：其中右子树6下的左子节点4 小于于根节点 5

方法一 [递归]

思路

递归需要两个辅助参数 lower与upper 代表下边界与上边界

1. val > lower && val < upper 当前节点值要大于下边界 并且小于上边界 如果不存在上边界和下边界则直接通过
2. 递归左子树和右子树 左子树以当前节点值为upper lower不变 右子树以当前节点值为lower upper不变

代码

var isValidBST1 = function(root,lower = null,upper = null) {
    if(root === null) return true;
    let val = root.val;
    if ((lower !== null && val <= lower) || (upper !== null&& val >= upper)) return false;
    if(!isValidBST(root.left,lower,val)) return false;
    if(!isValidBST(root.right,val,upper)) return false;
    return true;
};

方法二 [迭代]

思路

使用栈来表示层级 入栈的是一个数组形式存入其下边界与上边界

代码

var isValidBST = function(root) {
    if(root === null) return true;
    var stack = [[root, -Infinity, Infinity]];
    while(stack.length){
       let [root,lower,upper] = stack.pop();
        if(root == null){
            continue;
        }
        var val = root.val;
        if(val <= lower || val >= upper) return false;
        stack.push([root.right, val, upper]);
        stack.push([root.left, lower, val]);
    }
    return true;
};