golang 解法, 执行用时: 4 ms, 内存消耗: 5 MB, 提交时间: 2023-04-22 11:49:01

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func dfs(node *TreeNode) (int, int) {
    if node == nil {
        return math.MaxInt, math.MinInt
    }
    lMin, lMax := dfs(node.Left)
    rMin, rMax := dfs(node.Right)
    x := node.Val
    if x <= lMax || x >= rMin {
        return math.MinInt, math.MaxInt
    }
    return min(lMin, x), max(rMax, x)
}

func isValidBST(root *TreeNode) bool {
    _, mx := dfs(root)
    return mx != math.MaxInt
}

func min(a, b int) int { if b < a { return b }; return a }
func max(a, b int) int { if b > a { return b }; return a }

golang 解法, 执行用时: 0 ms, 内存消耗: 5 MB, 提交时间: 2023-04-22 11:48:49

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isValidBST(root *TreeNode) bool {
    pre := math.MinInt
    var dfs func(*TreeNode) bool
    dfs = func(node *TreeNode) bool {
        if node == nil {
            return true
        }
        if !dfs(node.Left) || node.Val <= pre {
            return false
        }
        pre = node.Val
        return dfs(node.Right)
    }
    return dfs(root)
}

golang 解法, 执行用时: 4 ms, 内存消耗: 4.9 MB, 提交时间: 2023-04-22 11:48:22

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func dfs(node *TreeNode, left, right int) bool {
    if node == nil {
        return true
    }
    x := node.Val
    return left < x && x < right &&
        dfs(node.Left, left, x) &&
        dfs(node.Right, x, right)
}

func isValidBST(root *TreeNode) bool {
    return dfs(root, math.MinInt, math.MaxInt)
}

java 解法, 执行用时: 0 ms, 内存消耗: 40.9 MB, 提交时间: 2023-04-22 11:48:06

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean isValidBST(TreeNode node, long left, long right) {
        if (node == null)
            return true;
        long x = node.val;
        return left < x && x < right &&
               isValidBST(node.left, left, x) &&
               isValidBST(node.right, x, right);
    }
}

java 解法, 执行用时: 0 ms, 内存消耗: 41.1 MB, 提交时间: 2023-04-22 11:47:55

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private long pre = Long.MIN_VALUE;

    public boolean isValidBST(TreeNode root) {
        if (root == null)
            return true;
        if (!isValidBST(root.left) || root.val <= pre)
            return false;
        pre = root.val;
        return isValidBST(root.right);
    }
}

java 解法, 执行用时: 0 ms, 内存消耗: 41.1 MB, 提交时间: 2023-04-22 11:47:43

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isValidBST(TreeNode root) {
        return dfs(root)[1] != Long.MAX_VALUE;
    }

    private long[] dfs(TreeNode node) {
        if (node == null)
            return new long[]{Long.MAX_VALUE, Long.MIN_VALUE};
        long[] left = dfs(node.left);
        long[] right = dfs(node.right);
        long x = node.val;
        // 也可以在递归完左子树之后立刻判断，如果不是二叉搜索树，就不用递归右子树了
        if (x <= left[1] || x >= right[0])
            return new long[]{Long.MIN_VALUE, Long.MAX_VALUE};
        return new long[]{Math.min(left[0], x), Math.max(right[1], x)};
    }
}

python3 解法, 执行用时: 40 ms, 内存消耗: 18.4 MB, 提交时间: 2023-04-22 11:47:28

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def dfs(node: Optional[TreeNode]) -> Tuple:
            if node is None:
                return inf, -inf
            l_min, l_max = dfs(node.left)
            r_min, r_max = dfs(node.right)
            x = node.val
            # 也可以在递归完左子树之后立刻判断，如果不是二叉搜索树，就不用递归右子树了
            if x <= l_max or x >= r_min:
                return -inf, inf
            return min(l_min, x), max(r_max, x)
        return dfs(root)[1] != inf

python3 解法, 执行用时: 56 ms, 内存消耗: 18.4 MB, 提交时间: 2023-04-22 11:47:13

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    pre = -inf
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        if root is None:
            return True
        if not self.isValidBST(root.left) or root.val <= self.pre:
            return False
        self.pre = root.val
        return self.isValidBST(root.right)

python3 解法, 执行用时: 40 ms, 内存消耗: 17.8 MB, 提交时间: 2023-04-22 11:47:00

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isValidBST(self, root: Optional[TreeNode], left=-inf, right=inf) -> bool:
        if root is None:
            return True
        x = root.val
        return left < x < right and \
               self.isValidBST(root.left, left, x) and \
               self.isValidBST(root.right, x, right)