LeetCode 98. Validate Binary Search Tree（二叉樹）

Validate Binary Search Tree

Medium

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

Input: [2,1,3]

Output: true

Example 2:

5

/

1 4

/

3 6

Input: [5,1,4,null,null,3,6]

Output: false

Explanation: The root node’s value is 5 but its right child’s value is 4.

題意

判斷二叉搜尋樹是否valid

思路

【思路一】

中序周遊BST，遞歸函數傳回一個對象(boolean isValid, int minVal, int maxVal)表示以root為根節點的子樹是否valid，最小值和最大值

【思路二】

中序周遊BST，維護一個Integer表示上次通路的值，左/右子樹不合法或pre < root.val則目前子樹不合法

思路一和思路二的時間複雜度都是O(n)，空間複雜度也都是O(n)，其中n為BST的節點個數。但是思路二的時間常數更小。

代碼

【思路一】

/*
 * @lc app=leetcode id=98 lang=java
 *
 * [98] Validate Binary Search Tree
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    class Result {
        boolean isValid;
        int minVal, maxVal;

        public Result(boolean isValid, int minVal, int maxVal) {
            this.isValid = isValid;
            this.minVal = minVal;
            this.maxVal = maxVal;
        }
    }

    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        return checkValidBST(root).isValid;
    }

    private Result checkValidBST(TreeNode root) {
        Result lres = null, rres = null;
        int minVal, maxVal;
        if (root.left != null) {
            lres = checkValidBST(root.left);
            if (!lres.isValid)
                return new Result(false, 0, 0);
        }
        if (root.right != null) {
            rres = checkValidBST(root.right);
            if (!rres.isValid)
                return new Result(false, 0, 0);
        }
        if (lres != null) {
            if (lres.maxVal >= root.val) {
                return new Result(false, 0, 0);
            }
            else {
                minVal = lres.minVal;
            }
        }
        else {
            minVal = root.val;
        }
        if (rres != null) {
            if (rres.minVal <= root.val) {
                return new Result(false, 0, 0);
            }
            else {
                maxVal = rres.maxVal;
            }
        }
        else {
            maxVal = root.val;
        }
        return new Result(true, minVal, maxVal);
    }
}
           

【思路二】

/*
 * @lc app=leetcode id=98 lang=java
 *
 * [98] Validate Binary Search Tree
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private Integer pre = null;

    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        return inorderTraversal(root);
    }

    private boolean inorderTraversal(TreeNode root) {
        if (root.left != null && !inorderTraversal(root.left)) {
            return false;
        }
        if (this.pre != null && this.pre >= root.val) {
            return false;
        } else {
            this.pre = root.val;
        }
        if (root.right != null && !inorderTraversal(root.right)) {
            return false;
        }
        return true;
    }
}