98.Validate Binary Search Tree
===

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

[98. Validate Binary Search Tree](https://leetcode.com/problems/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^4^].
* -2^31^ <= `Node.val` <= 2^31^ - 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]

> [name=玉山][time= 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
> [name=Kobe][time= 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;
            }
        }
    }
}

> [name=Jim][time= 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給大家笑一下
> [name=Marsgoat][time= Dec 7, 2022]

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)