leetcode98. Validate Binary Search Tree

songze 發(fā)布于2019-08-15 10:56 / 384人閱讀

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

題目要求

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.

判斷一個(gè)樹(shù)是否是二叉查找樹(shù)。二叉查找樹(shù)即滿(mǎn)足當(dāng)前節(jié)點(diǎn)左子樹(shù)的值均小于當(dāng)前節(jié)點(diǎn)的值，右子樹(shù)的值均大于當(dāng)前節(jié)點(diǎn)的值。

思路一：stack dfs

可以看到，對(duì)二叉查找樹(shù)的中序遍歷結(jié)果應(yīng)當(dāng)是一個(gè)遞增的數(shù)組。這里我們用堆棧的方式實(shí)現(xiàn)中序遍歷。

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

思路二：遞歸

我們可以發(fā)現(xiàn)，如果已知當(dāng)前節(jié)點(diǎn)的值val以及取值的上下限upper，lower，那么左子節(jié)點(diǎn)的取值范圍就是(lower, val),右子節(jié)點(diǎn)的取值范圍就是(val, upper)。由此出發(fā)遞歸判斷，時(shí)間復(fù)雜度為O(n)因?yàn)槊總€(gè)節(jié)點(diǎn)只需要遍歷一次。

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

想要了解更多開(kāi)發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號(hào)！將會(huì)不定期的發(fā)放福利哦~