Algorithm
本周选择的算法题是：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, 104]. -231 <= Node.val <= 231 - 1
Solution
边界迭代：
class Solution:
def isValidBST(self, root: TreeNode) -> bool:
stack = [(root, None, None)]
while stack:
node, min, max = stack.pop()
if node.right:
if node.right.val <= node.val: return False
if max and max <= node.right.val: return False
if node.right.left or node.right.right:
stack.append((node.right, node.val, max))
if node.left:
if node.left.val >= node.val: return False
if min and min >= node.left.val: return False
if node.left.left or node.left.right:
stack.append((node.left, min, node.val))
return True
中序遍历：
class Solution:
def isValidBST(self, root: TreeNode) -> bool:
stack, min = [], float('-inf')
while stack or root:
while root:
stack.append(root)
root = root.left
root = stack.pop()
if root.val <= min: return False
min, root = root.val, root.right
return True
Review
平庸不是问题，不自信才是。人生的旅程很长，并没有严格意义上的成功，我们甚至不需要做到最好，只需要不断尝试一些事情，找到自己真正感兴趣、哪怕是少有人做的事即可。
平庸和失败并不沾边。
Tip
想到了一种借助编译期能力的组件化方案，或许可以相对完美的解决现阶段的问题。