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 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

请勿发布不友善或者负能量的内容。与人为善,比聪明更重要!