98.validate-binary-search-tree

发表评论
371 views

 ›
98.validate-binary-search-tree

98. 验证二叉搜索树

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。 节点的右子树只包含大于当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。 示例 1:

输入:
    2
   / \
  1   3
输出: true

示例 2:

输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ，但是其右子节点值为 4 。

思路

  1. 中序遍历 => array，只保留一个前驱节点 O
  2. Recursion 
validate('', min, max) {
    max <- validate(node.left)
    min <- validate(node.right)
  }

  max < root, min > root

解法一

中序遍历

# 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: TreeNode) -> bool:
        inorder = self.inorder(root)
        return inorder == list(sorted(set(inorder))) # 这里复杂度过高

    def inorder(self, root):
        if root is None:
            return []
        return self.inorder(root.left) + [root.val] + self.inorder(root.right)

# 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: TreeNode) -> bool:
        self.prev = None
        return self.helper(root)

    def helper(self, root):
        if root is None:
            return True
        if not self.helper(root.left):
            return False
        if self.prev and  self.prev.val >= root.val:
            return False
        self.prev = root
        return self.helper(root.right)

# 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: TreeNode) -> bool:
      self.pre = TreeNode(float('-inf'))
      return self.inorder(root)

    def inorder(self, root) -> bool:
      if not root:
        return True

      if not self.inorder(root.left):
        return False

      if root.val <= self.pre.val:
        return False

      self.pre = root
      return self.inorder(root.right)

解法二

# 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: TreeNode) -> bool:
      return self.helper(root, float('-inf'), float('inf'))

    def helper(self, root, MIN, MAX):
      if not root:
        return True

      if root.val <= MIN or root.val >= MAX:
        return False

      return self.helper(root.left, MIN, root.val) and self.helper(root.right, root.val, MAX)

/**
 * 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 helper(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    public boolean helper(TreeNode node, long min, long max) {
        if (node == null) return true;
        if (node.val <= min || node.val >= max) return false;
        return helper(node.left, min, (long)node.val) && helper(node.right, (long)node.val, max);
    }
}