problem

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.

分析

使用递归算法，如果左子树和右子树都是二叉排序树且根节点大于左子树最大节点、小于右子树最小节点的话那么这棵树就是二叉排序树。

也可以这样想，如果所有节点都满足大于左子树最右节点、小于右子树最左节点那么这棵树也是二叉排序树。 下面是相应的代码，超过了90%的提交。

ps： 这两种想法实际上在转化为代码时都是相同的，这种殊途同归的现象在数学上应该就是递归和循环的转化关系，例如尾递归的优化。

补充，其实第二种想法转化为代码应该是循环的，即遍历所有节点看是否满足条件，之前错以为两者相同是因为在脑中直接把它转化为递归代码了。 实际上不用栈的话是无法将遍历二叉树的算法转化为循环算法的。

关于递归和循环的转化问题，在栈底不可预见的时候，递归是无法有效地化为循环的。Recursion Vs Loop，例如计算费波那切数列就可以有效地将递归转化为循环，而实际上不用栈的话是无法将遍历二叉树的算法转化为循环算法的。。

def valid(root): left = root.left right = root.right if left != None: while left.right: left = left.right if right != None: while right.left: right = right.left if left != None and left.val >= root.val : return False if right != None and right.val <= root.val: return False return True class Solution(object): def isValidBST(self, root): """ :type root: TreeNode :rtype: bool """ if root == None: return True #valid(root)性能更好 return valid(root) and self.isValidBST(root.left) and self.isValidBST(root.right)

二叉树先序遍历基本形式：

def traverse(root) if root: visit(root) traverse(root.left) traverse(root.right)

上面的程序就相当于：

“` def isValidBST(self, root):

if root == None: return True visit = valid(root) left = isValidBST(root.left) right = isValidBST(root.right) return visit and left and right

总结

和之前一样，在递归中使用变量保存子问题的结果，递归就是将原问题逐渐缩小规模，直至小到可以直接处理（例如本题中当树为空树时返回True），原问题的解可以由小规模问题的解得出（例如return visit and left and right），在缩小规模的过程中也可以加入一些处理，比如此题中的提前结束返回（当visit==False时）

递归的要素：

最上面是可以处理的最小问题，递归出口如果当前规模问题处理不了，就将其分解获得小规模问题的解，利用小规模问题的解计算出原问题的解。