成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

[Leetcode] Validate Binary Search Tree 驗(yàn)證二叉搜索樹

fuchenxuan / 1327人閱讀

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

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.
遞歸法 復(fù)雜度

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

思路

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

注意

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

不用再額外判斷左右節(jié)點(diǎn)和根節(jié)點(diǎn)的關(guān)系，因?yàn)槲覀兗尤肓薽ax和min，如果左節(jié)點(diǎn)大于根節(jié)點(diǎn)的話，下一輪就過不了max的檢查，右節(jié)點(diǎn)和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;
        }
        // 如果該節(jié)點(diǎn)大于上限 返回假
        if(max != null && root.val >= max){
            return false;
        }
        // 如果該節(jié)點(diǎn)小于下限 返回假
        if(min != null && root.val <= min){
            return false;
        }
        // 遞歸判斷左子樹和右子樹
        return isValidBST(root.left, root.val, min) && isValidBST(root.right, max, root.val);
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/64625.html

相關(guān)文章

  • leetcode98. Validate Binary Search Tree

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

    codercao 評(píng)論0 收藏0

  • leetcode98. Validate Binary Search Tree

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

    AlphaWatch 評(píng)論0 收藏0

  • leetcode98. Validate Binary Search Tree

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

    songze 評(píng)論0 收藏0

  • LeetCode 之 JavaScript 解答第98題 —— 驗(yàn)證二叉搜索樹

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

    用戶84 評(píng)論0 收藏0

  • 前端 | 每天一個(gè) LeetCode

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

    張漢慶 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<