LeetCode 之 JavaScript 解答第98題 —— 驗證二叉搜索樹

用戶84 發布于2019-08-23 17:12 / 574人閱讀

摘要：小鹿題目驗證二叉搜索樹給定一個二叉樹，判斷其是否是一個有效的二叉搜索樹。假設一個二叉搜索樹具有如下特征節點的左子樹只包含小于當前節點的數。所有左子樹和右子樹自身必須也是二叉搜索樹。算法思路定義全局的變量，用來返回是否為二叉搜索樹。

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云服務器二叉樹排序樹規則二叉查找樹二叉排序樹二叉樹遍歷

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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