[LeetCode] 98. Validate Binary Search Tree

轉自LeetCode

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

Assume a 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:

    2
   / \
  1   3

Binary tree [2,1,3], return true.

Example 2:

    1
   / \
  2   3

Binary tree [1,2,3], return false.

<Solution>

這題要來確認 input 給的 BST 是不是符合規則的

看個例子

       5
     /   \
    3     8
   / \   / \
  0   4 6  10

先注意到一點，題目規範的 BST 是不會有重複元素出現的，只有大於小於，沒有等於的問題

因此，可以用 inorder traversal 來歷遍每個 node，並檢查是否符合遞增數列的走向

因為每個 subtree 都也要符合題目BST的規則，所以用 inorder traversal 來看，output會是一個遞增數列

0 3 4 5 6 8 10

code 如下(參考資料)

這題理論上是可以用 morris traversal 的，但在 LeetCode 的環境跑，一直都會有 run time error

看到別人也有遇到同樣問題，所以就先放棄 morris traversal 的解法

這邊還有一種想法，是利用 BST 的本質，就是 left node < root node < right node

利用這個本質特性，搭配遞迴去檢查 left subtree 和 right subtree，來看整個 tree 是否是合法的 BST

這邊使用 long 來存放最大最小值，是為了包含 int 的最大最小值的邊界檢查

code 如下
c++

kotlin