本文共 3792 字，大约阅读时间需要 12 分钟。

• ：返回由[1,2,…,n]组成的所有二叉搜索树的列表，Medium.

思路：先确定root，在递归获取root.left和root.right

# Definition for a binary tree node.# class TreeNode(object):#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass Solution(object):    def generateTrees(self, n):        """        :type n: int        :rtype: List[TreeNode]        """        arrays = [i for i in range(1,n+1)]        return self.dp(arrays)    def dp(self,arrays):        if len(arrays) == 1:            return [TreeNode(arrays[0])]        ret = []        for k in range(len(arrays)):            num = arrays[k]            l = arrays[0:k]            r = arrays[k+1:]            left = self.dp(l)            right = self.dp(r)            if left == []:                for j in range(len(right)):                    Node = TreeNode(num)                    Node.right = right[j]                    ret.append(Node)            if right == []:                for i in range(len(left)):                    Node = TreeNode(num)                    Node.left = left[i]                    ret.append(Node)            for i in range(len(left)):                for j in range(len(right)):                    Node = TreeNode(num)                    Node.left = left[i]                    Node.right = right[j]                    ret.append(Node)        return ret

• ：交换树上两个节点的值，使得这棵树成为二叉搜索树。Hard

二叉搜索树的性质是中序遍历结果为有序数组，利用这个性质先获取原树中序遍历的结果，然后寻找最高波峰和最低低谷，再用dfs来修正原来的树即可

# Definition for a binary tree node.# class TreeNode(object):#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneimport sysclass Solution(object):    def recoverTree(self, root):        """        :type root: TreeNode        :rtype: void Do not return anything, modify root in-place instead.        """        stack = [root]        arrays = [-sys.maxint]        while(stack):            item = stack.pop()            if item.left == None and item.right == None:                arrays.append(item.val)            else:                if item.right:                    stack.append(item.right)                stack.append(TreeNode(item.val))                if item.left:                    stack.append(item.left)        arrays.append(sys.maxint)        val1,val2 = -sys.maxint,sys.maxint        for i in range(1,len(arrays)-1):            if arrays[i]>arrays[i-1] and arrays[i]>arrays[i+1] and arrays[i]>val1:                val1 = arrays[i]            if arrays[i]

• ：判断二叉树是否是有效的二叉搜索树，Medium

设置最大最小边界进行递归判断

# Definition for a binary tree node.# class TreeNode(object):#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneimport sysclass Solution(object):    def isValidBST(self, root):        """        :type root: TreeNode        :rtype: bool        """        min_ = -sys.maxint        max_ = sys.maxint        return self.checkBST(root,min_,max_)    def checkBST(self,root,min_,max_):        if root is None: return True        if root.val <= min_ or root.val >= max_:            return False        return self.checkBST(root.left,min_,root.val) and self.checkBST(root.right,root.val,max_)

• ：给树剪枝，如果该节点的值和其子孙节点的值均为0，则溢出该节点，Medium

计算节点的值为该节点的值+所有子孙节点值的和

# Definition for a binary tree node.# class TreeNode(object):#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass Solution(object):    def pruneTree(self, root):        """        :type root: TreeNode        :rtype: TreeNode        """        if self.nodeValues(root) == 0: return None        root.left = self.pruneTree(root.left)        root.right = self.pruneTree(root.right)        return root    def nodeValues(self,root):        if root is None: return 0        return root.val+self.nodeValues(root.left)+self.nodeValues(root.right)

转载地址：http://pbqmi.baihongyu.com/