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.

*A subtree of treeName is a tree consisting of a node in treeName and all of its descendants.

規則

#   5
#  / \
# 4   7
# passed

#   5
#  / \
# 4   7
#    /
#   2
# no passed

測試案例

Input: root = [2,1,3]
Output: true
Input: root = [5,1,4,null,null,3,6]
Output: false

思路

  1. 創建 node 來置放二元樹節點
  2. 驗證節點符合左邊小右邊大平衡
  3. 如果底下還有節點則繼續判斷，並且一樣符合左邊小右邊大平衡

實作

#   5
#  / \
# 4   7
node = Node(5)
node.left = Node(4)
node.right = Node(7)
print(Solution().isValidBST(node))
# True

#   5
#  / \
# 4   7
#    /
#   2
node = Node(5)
node.left = Node(4)
node.right = Node(7)
node.right.left = Node(2)
print(Solution().isValidBST(node))
# False

創建 node 來置放二元樹節點

class Node(object):
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

驗證節點符合左邊小右邊大平衡

創建 helper，此目的是為了後續如果要添加額外參數時方便調用，也可以直接在裡面實作; 傳入生成節點與左邊值與右邊值。

float(’-inf’)=負無窮大, float(‘inf’)=正無窮大 | 用來定義邊界值

這邊是核心判斷，但只會驗證傳入 node，而不會繼續往下驗證左節點與右節點，所以必須繼續拓展。

def _isValidBST(self, node, low, high):
    val = node.val
    if (val > low and val < high):
        return True
    return False

首先先驗證左節點，根據規則是他總是要比父節點小，這邊用到 recursive 的邏輯會讓代碼更加簡潔：

if (
     (val > low and val < high) and
      # check if left subtrees are valid
      self._isValidBST(node.left, low, val)
      ):
            return True
        return False

將左節點傳入原本判斷，最小邊界維持負無窮大，而最大邊界則是為父節點來符合條件。

接著驗證右節點，依樣畫葫蘆; 只是這次最小邊界為父節點，而最大邊界則為正無窮大。

if (
     (val > low and val < high) and
      # check if left subtrees are valid
      self._isValidBST(node.left, low, val) and
      # check if right subtrees are valid
      self._isValidBST(node.left, val, high)
      ):
            return True
        return False

一旦遍歷完所有節點並且符合規則，那就是一個驗證通過的二元搜尋樹。

接著處理當遍歷到底時，已經沒有節點的處理：

def _isValidBST(self, node, low, high):
    # 已經沒有節點可判斷，返回 True
    if not node:
        return True

完整代碼

class Node(object):
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution(object):
    def _isValidBST(self, node, low, high):
        if not node:
            return True
        val = node.val
        if (
            # rule
            (val > low and val < high) and
            # check if left and right subtrees are valid
            self._isValidBST(node.left, low, val) and
            self._isValidBST(node.right, val, high)
            ):
            # all conditions are met, confirm.
            return True
        return False
    def isValidBST(self, node):
        return self._isValidBST(node, float('-inf'), float('inf'))