[Leetcode] Validate Binary Search Tree 驗證二叉搜索樹

fuchenxuan 發布于2019-08-14 12:40 / 1319人閱讀

摘要：注意這里的結構和不同的二叉樹遍歷一樣，如果到空節點就返回，否則遞歸遍歷左節點和右節點。唯一不同是加入了和，所以要在遞歸之前先判斷是否符合和的條件。代碼如果該節點大于上限返回假如果該節點小于下限返回假遞歸判斷左子樹和右子樹

Validate 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.

遞歸法 復雜度

時間 O(N) 空間 O(H) 遞歸棧空間

思路

遞歸的判斷每個節點是否滿足BST的要求，需要注意的是BST的要求不只是左節點小于根節點小于右節點，還有個隱含的條件是，左子樹里所有節點都要小于根節點，而右子樹里所有節點都要大于根節點。所以我們要把這個上限和下限代入遞歸中。

注意

這里的結構和不同的二叉樹遍歷一樣，如果到空節點就返回，否則遞歸遍歷左節點和右節點。唯一不同是加入了max和min，所以要在遞歸之前先判斷是否符合max和min的條件。

不用再額外判斷左右節點和根節點的關系，因為我們加入了max和min，如果左節點大于根節點的話，下一輪就過不了max的檢查，右節點和min同理。

代碼

public class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, null, null);
    }
    
    private boolean isValidBST(TreeNode root, Integer max, Integer min){
        if(root == null){
            return true;
        }
        // 如果該節點大于上限 返回假
        if(max != null && root.val >= max){
            return false;
        }
        // 如果該節點小于下限 返回假
        if(min != null && root.val <= min){
            return false;
        }
        // 遞歸判斷左子樹和右子樹
        return isValidBST(root.left, root.val, min) && isValidBST(root.right, max, root.val);
    }
}

云服務器 GPU云服務器 binary-search-tree binary-tree binary-search php tree 樹

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/64625.html

leetcode98. Validate Binary Search Tree

摘要：題目要求檢驗二叉查找樹是否符合規則。二叉查找樹是指當前節點左子樹上的值均比其小，右子樹上的值均比起大。因此在這里我們采用棧的方式實現中序遍歷，通過研究中序遍歷是否遞增來判斷二叉查找樹是否符合規則。題目要求 Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is...

codercao 2019-08-15 10:56 評論0 收藏0
leetcode98. Validate Binary Search Tree

摘要：題目要求檢驗二叉查找樹是否符合規則。二叉查找樹是指當前節點左子樹上的值均比其小，右子樹上的值均比起大。因此在這里我們采用棧的方式實現中序遍歷，通過研究中序遍歷是否遞增來判斷二叉查找樹是否符合規則。題目要求 Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is...

AlphaWatch 2019-08-15 10:56 評論0 收藏0
leetcode98. Validate Binary Search Tree

摘要：題目要求判斷一個樹是否是二叉查找樹。二叉查找樹即滿足當前節點左子樹的值均小于當前節點的值，右子樹的值均大于當前節點的值。思路一可以看到，對二叉查找樹的中序遍歷結果應當是一個遞增的數組。這里我們用堆棧的方式實現中序遍歷。題目要求 given a binary tree, determine if it is a valid binary search tree (BST). Assu...

songze 2019-08-15 10:56 評論0 收藏0
LeetCode 之 JavaScript 解答第98題 —— 驗證二叉搜索樹

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

用戶84 2019-08-23 17:12 評論0 收藏0
前端 | 每天一個 LeetCode

摘要：在線網站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項目地址歡迎一起交流學習。這篇文章記錄我練習的 LeetCode 題目，語言 JavaScript。在線網站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...

張漢慶 2019-08-23 13:42 評論0 收藏0