LeetCode 98. Validate Binary Search Tree

解法一

思路

中序遍历BST可以得到有序数组，所以如果遍历时前一个数比后一个数大的话，就不是 valid 了。

代码

class Solution {
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;
        TreeNode prev = null;

        // Do an inorder traversal
        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }

            curr = stack.pop();
            if (prev != null && prev.val >= curr.val) {
                return false;
            }
            prev = curr;
            curr = curr.right;
        }
        return true;
    }
}

复杂度分析

• 时间复杂度
  • 遍历一遍二叉树，花费 O(n) 时间
• 空间复杂度
  • O(N) – Stack

解法二

思路

写一个 helper function, 先检查该结点是否比 upper bound 小，以及比 lower bound 大；然后递归调用检查其左子树和右子树。

代码

class Solution {
    public boolean isValidBST(TreeNode root) {
        return helper(root, null, null);
    }

    private boolean helper(TreeNode node, Integer lower, Integer upper) {
        if (node == null) return true;
        int val = node.val;
        if (lower != null && val <= lower) return false;
        if (upper != null && val >= upper) return false;

        // recursively check left and right subtree
        if (!helper(node.left, lower, val)) return false;
        if (!helper(node.right, val, upper)) return false;

        return true;
    }
}

复杂度分析

• 时间复杂度
  • O(n)
• 空间复杂度
  • O(n)

Takeaway

由于是 BST，必须保证每一个节点的所有左孩子比它小，右孩子比它大。

本作品采用《CC 协议》，转载必须注明作者和本文链接