leetcode98. Validate Binary Search Tree

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

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

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

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

如果了解中序遍歷的同學(xué)可以知道，一顆二叉查找樹的中序遍歷結(jié)果應(yīng)當(dāng)是一個(gè)數(shù)值有小到大遞增的數(shù)組。正因?yàn)橹行虮闅v是指先遍歷左子樹，接著遍歷中間節(jié)點(diǎn)，再遍歷右子樹，恰好和查找樹的值遞增順序相同。因此在這里我們采用棧的方式實(shí)現(xiàn)中序遍歷，通過(guò)研究中序遍歷是否遞增來(lái)判斷二叉查找樹是否符合規(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)先算法

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