国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

leetcode98. Validate Binary Search Tree

codercao / 3035人閱讀

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

題目要求 
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.

檢驗二叉查找樹是否符合規則。二叉查找樹是指當前節點左子樹上的值均比其小，右子樹上的值均比起大。

思路一：stack 深度優先算法

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

    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，以免出現Integer.MIN_VALUE的誤判
思路二：遞歸 深度優先算法

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

    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);
    }

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

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

相關文章

  • leetcode98. Validate Binary Search Tree

    摘要：題目要求檢驗二叉查找樹是否符合規則。二叉查找樹是指當前節點左子樹上的值均比其小，右子樹上的值均比起大。因此在這里我們采用棧的方式實現中序遍歷，通過研究中序遍歷是否遞增來判斷二叉查找樹是否符合規則。 題目要求 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

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

    songze 評論0 收藏0

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

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

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

    用戶84 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<