LeetCode 之 JavaScript 解答第98题 —— 验证二叉搜索树

用户84 发布于2019-08-23 17:12 / 573人阅读

摘要：小鹿题目验证二叉搜索树给定一个二叉树，判断其是否是一个有效的二叉搜索树。假设一个二叉搜索树具有如下特征节点的左子树只包含小于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。算法思路定义全局的变量，用来返回是否为二叉搜索树。

Time：2019/4/24
Title: Vaildata Binary Search Tree
Difficulty: Medium
Author: 小鹿

题目：Vaildata Binary Search Tree（验证二叉搜索树）

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node"s key.

The right subtree of a node contains only nodes with keys greater than the node"s key.

Both the left and right subtrees must also be binary search trees.

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

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

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

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

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

Example 1:

Input:
    2
   / 
  1   3
Output: true

Example 2:

    5
   / 
  1   4
     / 
    3   6
Output: false
Explanation: The input is: [5,1,4,null,null,3,6]. The root node"s value
             is 5 but its right child"s value is 4.

Solve:

▉ 问题分析

看到此题的入手点就是上方提出的三点二叉搜索树的三点要求：

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

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

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

1）以上三点要求最容易解决的就是一个中序遍历，判断遍历出的每个元素后一个元素是否大于前一个元素，如果不符合条件，那么就不是一个二分搜索树。

▉ 算法思路

1）定义全局的 boolean 变量，用来返回是否为二叉搜索树。

2）定义一个边界值赋予 max 变量。每遍历一次，如果符合前后大小的要求，就将当前节点的值赋值给 max 变量，用于下一次遍历的结点的大小比较。如果不符合要求，我们将其布尔变量置为 false。

3）整个过程是用递归来解决的，在理解上还是有点不符合常规思路的。也是整个问题分析中最重要的一点。

▉ 代码实现

var isValidBST = function(root) {
    // boolean 变量
    let isValidBSTFlag = true;
    // 最大值变量
    let max = -Number.MAX_VALUE;
    const orderSearch = root => {
        // 终止条件（判断当前结点是否为 null）
        if (root) {
            // 中序遍历
            orderSearch(root.left);
            // 判断遍历前后的值是否逐渐升序
            if (root.val > max) {
                // 存储当前结点值，进行下一次比较
                max = root.val;
            } else {
                // 当前节点值小于前一结点值，返回 false
                isValidBSTFlag = false;
            }
            orderSearch(root.right);
        }
    }
    orderSearch(root);
    return isValidBSTFlag;
};

欢迎一起加入到 LeetCode 开源 Github 仓库，可以向 me 提交您其他语言的代码。在仓库上坚持和小伙伴们一起打卡，共同完善我们的开源小仓库！
Github：https://github.com/luxiangqia...
欢迎关注我个人公众号：「一个不甘平凡的码农」，记录了自己一路自学编程的故事。

云服务器 GPU云服务器二叉树排序树规则二叉查找树二叉排序树二叉树遍历

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/103986.html

LeetCode 之 JavaScript 解答第112题 —— 路径总和（Path Sum）

摘要：小鹿题目路径总和给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。说明叶子节点是指没有子节点的节点。 Time：2019/4/26Title: Path SumDifficulty: EasyAuthor: 小鹿题目：Path Sum（路径总和） Given a binary tree and a sum, determin...

lylwyy2016 2019-08-26 13:44 评论0 收藏0
LeetCode 之 JavaScript 解答第94题 —— 二叉树的中序遍历

摘要：小鹿题目二叉树中序遍历给定一个二叉树，返回它的中序遍历。通常递归的方法解决二叉树的遍历最方便不过，但是我还是喜欢增加点难度，用一般的迭代循环来实现。 Time：2019/4/25Title:Binary Tree Inorder TraversalDifficulty: MediumAuthor:小鹿题目：Binary Tree Inorder Traversal（二叉树中序遍历...

Jason 2019-08-23 17:19 评论0 收藏0
LeetCode 之 JavaScript 解答第226题 —— 翻转二叉树（Invert Bina

摘要：算法思路判断树是否为空同时也是终止条件。分别对左右子树进行递归。代码实现判断当前树是否为左右子树结点交换分别对左右子树进行递归返回树的根节点欢迎一起加入到开源仓库，可以向提交您其他语言的代码。 Time：2019/4/21Title: Invert Binary TreeDifficulty: EasyAuthor: 小鹿题目：Invert Binary Tree（反转二叉树） ...

MingjunYang 2019-08-23 17:07 评论0 收藏0
LeetCode 之 JavaScript 解答第104题 —— 二叉树的最大深度

摘要：小鹿题目二叉树的最大深度给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。求二叉树的深度，必然要用到递归来解决。分别递归左右子树。 Time：2019/4/22Title: Maximum Depth of Binary TreeDifficulty: MediumAuthor:小鹿题目：Maximum Depth of Binary Tre...

boredream 2019-08-23 17:07 评论0 收藏0
＜LeetCode天梯＞Day031 验证二叉搜索树（递归+中序遍历） | 初级算法 | Pytho

摘要：有效二叉搜索树定义如下节点的左子树只包含小于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。而我们二叉搜索树保证了左子树的节点的值均小于根节点的值，根节点的值均小于右子树的值，因此中序遍历以后得到的序列一定是升序序列。 ...

Genng 2021-11-24 09:39 评论0 收藏0