Basics

Binary Tree traversal， 我们来写一个用generator的。

def inorder(self, root):
    if root:
        for val in self.iterate(root.left):
            yield val
        yield root.val
        for val in self.iterate(root.right):
            yield val

Iteration inorder Treversal

class Solution(object):  #iterative
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root: return []
        res = []
        s = []
        while s or root:        
            while root:
                s.append(root)
                root = root.left
            tmp = s.pop()
            res.append(tmp.val)
            if tmp.right:
                root = tmp.right
        return res

Validate Binary Search Tree

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def isValidBST(self, root, left=-(1<<31+1), right=1<<31):
        """
        :type root: TreeNode
        :rtype: bool
        """

        if not root:
            return True

        if not left < root.val < right:
            return False

        return self.isValidBST(root.left, left, root.val) and self.isValidBST(root.right, root.val, right)

另一种解法

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

class Solution(object):

    pre = None
    def validBST(self, root):

        return self.inorder(root)

    def inorder(self, root):
        if root:
            if not self.inorder(root.left):
                return False
            if self.pre and root.val<self.pre:
                return False
            self.pre = root.val
            if not self.inorder(root.right):
                return False
        return True


a = TreeNode(1)
b = TreeNode(2)
c = TreeNode(3)
b.left, b.right = a, c
s = Solution()
ans = s.inorder(b)
print ans