98.Validate Binary Search Tree

tags: Medium,Tree,Binary Tree,DFS,Binary Search Tree

98. Validate Binary Search Tree

題目描述

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid 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:

Input: root = [2,1,3]
Output: true

Example 2:

Input: root = [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.

Constraints:

• The number of nodes in the tree is in the range [1, 10⁴].
• -2³¹ <= Node.val <= 2³¹ - 1

解答

Python

醜哭 recursive.

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:

        def recursive(root):
            print(root.val)
            if root.left == None and root.right == None:
                return (True, root.val, root.val)
            elif root.left != None and root.right == None:
                (T, left_max, left_min) = recursive(root.left)
                if T == False:
                    return (False,-1,-1)
                elif left_max >= root.val:
                    return (False,-1,-1)
                else:
                    return (True, root.val, left_min)

            elif root.left == None and root.right != None:
                (T, right_max, right_min) = recursive(root.right)
                if T == False:
                    return (False,-1,-1)
                elif right_min <= root.val:
                    return (False,-1,-1)
                else:
                    return (True, right_max, root.val)
            
            else:
                (Tr, right_max, right_min) = recursive(root.right)
                (Tl, left_max, left_min) = recursive(root.left)
                if Tr == False or Tl == False:
                    return (False,-1,-1)
                elif left_max < root.val and root.val < right_min:
                    return (True, right_max, left_min )
                else:
                    return (False,-1,-1)

        print(root)
        r = recursive(root)
        print(r[0])
        return r[0]

玉山 Dec 7, 2022

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def __init__(self):
        self.prev = -math.inf
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True

        # Inorder Traversal
        if not self.isValidBST(root.left):
            return False
        
        if root.val <= self.prev:
            return False
        self.prev = root.val

        return self.isValidBST(root.right)

來自樓下的靈感XD
Kobe Dec 9, 2022

C#

Inorder Traversal

public class Solution {
    public bool IsValidBST(TreeNode root) {
        int? lastVal = null;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        
        StackAllLeftNode(root);

        while (stack.Count > 0) {
            TreeNode target = stack.Pop();

            if (lastVal.HasValue && lastVal.Value >= target.val) {
                return false;
            }

            lastVal = target.val;

            StackAllLeftNode(target.right);
        }

        return true;

        void StackAllLeftNode(TreeNode node) {
            while(node != null) {
                stack.Push(node);
                node = node.left;
            }
        }
    }
}

Jim Dec 7, 2022

Javascript

function isValidBST(root) {
  const stack = [];
  let prev = null;
  while (root !== null || stack.length > 0) {
    while (root !== null) {
      stack.push(root);
      root = root.left;
    }
      
    root = stack.pop();
    if (prev !== null && root.val <= prev.val) return false;
    prev = root;
    root = root.right;
  }

  return true;
}

參考俊豪學長的答案，感覺比玉山的優美XDD
本來寫得很白癡以為可以，我放在discord給大家笑一下
Marsgoat Dec 7, 2022

Reference

回到題目列表