Skip to content

Latest commit

 

History

History
366 lines (305 loc) · 8.96 KB

98.validate-binary-search-tree.md

File metadata and controls

366 lines (305 loc) · 8.96 KB
Raw

题目地址(98. 验证二叉搜索树)

https://leetcode-cn.com/problems/validate-binary-search-tree/

题目描述

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

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

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

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

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

前置知识

  • 中序遍历

公司

  • 阿里
  • 腾讯
  • 百度
  • 字节

思路

中序遍历

这道题是让你验证一棵树是否为二叉查找树（BST）。 由于中序遍历的性质如果一个树遍历的结果是有序数组，那么他也是一个二叉查找树(BST), 我们只需要中序遍历，然后两两判断是否有逆序的元素对即可，如果有，则不是 BST，否则即为一个 BST。

定义法

根据定义，一个结点若是在根的左子树上，那它应该小于根结点的值而大于左子树最小值；若是在根的右子树上，那它应该大于根结点的值而小于右子树最大值。也就是说，每一个结点必须落在某个取值范围：

  1. 根结点的取值范围为（考虑某个结点为最大或最小整数的情况）：(long_min, long_max)
  2. 左子树的取值范围为：(current_min, root.value)
  3. 右子树的取值范围为：(root.value, current_max)

关键点解析

  • 二叉树的基本操作（遍历）
  • 中序遍历一个二叉查找树（BST）的结果是一个有序数组
  • 如果一个树遍历的结果是有序数组，那么他也是一个二叉查找树(BST)

代码

中序遍历

  • 语言支持：JS，C++, Java

JavaScript Code：

/*
 * @lc app=leetcode id=98 lang=javascript
 *
 * [98] Validate Binary Search Tree
 */
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function (root) {
  if (root === null) return true;
  if (root.left === null && root.right === null) return true;
  const stack = [root];
  let cur = root;
  let pre = null;

  function insertAllLefts(cur) {
    while (cur && cur.left) {
      const l = cur.left;
      stack.push(l);
      cur = l;
    }
  }
  insertAllLefts(cur);

  while ((cur = stack.pop())) {
    if (pre && cur.val <= pre.val) return false;
    const r = cur.right;

    if (r) {
      stack.push(r);
      insertAllLefts(r);
    }
    pre = cur;
  }

  return true;
};

C++ Code：

// 递归
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        TreeNode* prev = nullptr;
        return validateBstInorder(root, prev);
    }

private:
    bool validateBstInorder(TreeNode* root, TreeNode*& prev) {
        if (root == nullptr) return true;
        if (!validateBstInorder(root->left, prev)) return false;
        if (prev != nullptr && prev->val >= root->val) return false;
        prev = root;
        return validateBstInorder(root->right, prev);
    }
};

// 迭代
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        auto s = vector<TreeNode*>();
        TreeNode* prev = nullptr;
        while (root != nullptr || !s.empty()) {
            while (root != nullptr) {
                s.push_back(root);
                root = root->left;
            }
            root = s.back();
            s.pop_back();
            if (prev != nullptr && prev->val >= root->val) return false;
            prev = root;
            root = root->right;
        }
        return true;
    }
};

Java Code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isValidBST(TreeNode root) {
        Stack<Integer> stack = new Stack<> ();
        TreeNode previous = null;

        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if (previous != null && root.val <= previous.val ) return false;
            previous = root;
            root = root.right;
        }
        return true;
    }
}

定义法

  • 语言支持：C++，Python3, Java, JS

C++ Code：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
// 递归
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return helper(root, LONG_MIN, LONG_MAX);
    }
private:
    bool helper(const TreeNode* root, long min, long max) {
        if (root == nullptr) return true;
        if (root->val >= max || root->val <= min) return false;
        return helper(root->left, min, root->val) && helper(root->right, root->val, max);
    }
};

// 循环
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if (root == nullptr) return true;
        auto ranges = queue<pair<long, long>>();
        ranges.push(make_pair(LONG_MIN, LONG_MAX));
        auto nodes = queue<const TreeNode*>();
        nodes.push(root);
        while (!nodes.empty()) {
            auto sz = nodes.size();
            for (auto i = 0; i < sz; ++i) {
                auto range = ranges.front();
                ranges.pop();
                auto n = nodes.front();
                nodes.pop();
                if (n->val >= range.second || n->val <= range.first) {
                    return false;
                }
                if (n->left != nullptr) {
                    ranges.push(make_pair(range.first, n->val));
                    nodes.push(n->left);
                }
                if (n->right != nullptr) {
                    ranges.push(make_pair(n->val, range.second));
                    nodes.push(n->right);
                }
            }
        }
        return true;
    }
};

Python Code:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isValidBST(self, root: TreeNode, area: tuple=(-float('inf'), float('inf'))) -> bool:
        """思路如上面的分析，用Python表达会非常直白
        :param root TreeNode 节点
        :param area tuple 取值区间
        """
        if root is None:
            return True

        is_valid_left = root.left is None or\
                   (root.left.val < root.val and area[0] < root.left.val < area[1])
        is_valid_right = root.right is None or\
                   (root.right.val > root.val and area[0] < root.right.val < area[1])

        # 左右节点都符合，说明本节点符合要求
        is_valid = is_valid_left and is_valid_right

        # 递归下去
        return is_valid\
            and self.isValidBST(root.left, (area[0], root.val))\
            and self.isValidBST(root.right, (root.val, area[1]))

Java Code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isValidBST(TreeNode root) {
        return helper(root, null, null);
    }

    private boolean helper(TreeNode root, Integer lower, Integer higher) {
        if (root == null) return true;

        if (lower != null && root.val <= lower) return false;
        if (higher != null && root.val >= higher) return false;

        if (!helper(root.left, lower, root.val)) return false;
        if (!helper(root.right, root.val, higher)) return false;

        return true;
    }
}

JavaScript Code:

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function (root) {
  if (!root) return true;
  return valid(root);
};

function valid(root, min = -Infinity, max = Infinity) {
  if (!root) return true;
  const val = root.val;
  if (val <= min) return false;
  if (val >= max) return false;
  return valid(root.left, min, val) && valid(root.right, val, max);
}

复杂度分析

  • 时间复杂度：$O(N)$
  • 空间复杂度：$O(N)$

相关题目

230.kth-smallest-element-in-a-bst

大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。