成人无码视频,亚洲精品久久久久av无码,午夜精品久久久久久毛片,亚洲 中文字幕 日韩 无码

資訊專欄INFORMATION COLUMN

leetcode98. Validate Binary Search Tree

codercao / 3074人閱讀

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

題目要求 
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:
    2
   / 
  1   3
Binary tree [2,1,3], return true.
Example 2:
    1
   / 
  2   3
Binary tree [1,2,3], return false.

檢驗二叉查找樹是否符合規(guī)則。二叉查找樹是指當(dāng)前節(jié)點左子樹上的值均比其小，右子樹上的值均比起大。

思路一：stack 深度優(yōu)先算法

如果了解中序遍歷的同學(xué)可以知道，一顆二叉查找樹的中序遍歷結(jié)果應(yīng)當(dāng)是一個數(shù)值有小到大遞增的數(shù)組。正因為中序遍歷是指先遍歷左子樹，接著遍歷中間節(jié)點，再遍歷右子樹，恰好和查找樹的值遞增順序相同。因此在這里我們采用棧的方式實現(xiàn)中序遍歷，通過研究中序遍歷是否遞增來判斷二叉查找樹是否符合規(guī)則。代碼如下：

    public boolean isValidBST(TreeNode root) {
        long currentVal = Long.MIN_VALUE;
        LinkedList stack = new LinkedList();
        while(root!=null || !stack.isEmpty()){
            while(root!=null){
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if(root.val<=currentVal) return false;
            currentVal = root.val;
            root = root.right;
        }
        return true;
    }
這里需要注意的是，將最小值取為Long.MIN_VALUE，以免出現(xiàn)Integer.MIN_VALUE的誤判
思路二：遞歸 深度優(yōu)先算法

我們知道，任何一個二叉查找樹的節(jié)點都有一個取值區(qū)間，如果我們能夠找到該節(jié)點的取值區(qū)間以及其左右子節(jié)點對應(yīng)的取值區(qū)間，就可以遞歸的判斷該樹是否是一顆二叉查找樹。為了實現(xiàn)遞歸，我們需要找到其中的一般情況。假設(shè)我們已經(jīng)知道了當(dāng)前節(jié)點的區(qū)間，那么左子節(jié)點的上限即為父節(jié)點的值，而下限則應(yīng)該為父節(jié)點的下限。同理，右子節(jié)點的下限是父節(jié)點的值，而上限也就是父節(jié)點的上線。
代碼如下:

    public boolean isValidBST2(TreeNode root){
        return isValid(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    
    public boolean isValid(TreeNode treeNode, long lowerBound, long upperBound){
        if(treeNode==null) return true;
        if(treeNode.val>=upperBound || treeNode.val<=lowerBound) return false;
        return isValid(treeNode.left, lowerBound,treeNode.val) && isValid(treeNode.right, treeNode.val, upperBound);
    }

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

轉(zhuǎn)載請注明本文地址：http://m.hztianpu.com/yun/67433.html

相關(guān)文章

  • leetcode98. Validate Binary Search Tree

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

    AlphaWatch 評論0 收藏0

  • leetcode98. Validate Binary Search Tree

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

    songze 評論0 收藏0

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

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

    fuchenxuan 評論0 收藏0

  • [LeetCode] Largest BST Subtree

    Largest BST Subtree Given a binary tree, find the largest subtree which is a Binary Search Tree (BST), where largest means subtree with largest number of nodes in it. Note: A subtree must include all ...

    Youngdze 評論0 收藏0

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

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

    用戶84 評論0 收藏0

發(fā)表評論

0條評論

閱讀需要支付1元查看
<