tree_special

目录

• 95. Unique Binary Search Trees II （important）

求解树类型的题目，主要需要把握一下几个关键：
1、递归
2、三种树遍历方法。

96. Unique Binary Search Trees

Given n, how many structurally unique BST's (binary search trees) that store values 1...n?
For example,
Given n = 3, there are a total of 5 unique BST's.

是一个递归求解思路。f(4) = f(0)f(3) + f(1)f(2) + f(2)f(1) + f(3)f(0)。因为取定一个顶节点，两边的数是固定的。但是总数加起来固定，并且每边的排列组合可以递归求出。

class Solution(object):
    _lookup = {0:1, 1:1, 2:2}
    def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n == 0 or n == 1:
            return 1
        if n == 2:
            return 2
        res = 0
        for i in xrange(0, n):
            if i in self._lookup:
                a = self._lookup[i]
            else:
                a = self.numTrees(i)
            if n-i-1 in self._lookup:
                b = self._lookup[n-i-1]
            else:
                b = self.numTrees(n-i-1)
            res += a * b
        self._lookup[n] = res
        return res

95. Unique Binary Search Trees II ****

Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1...n.
For example,
Given n = 3, your program should return all 5 unique BST's shown below.

使用dsf进行求解（求个数一般使用递归，若枚举可考虑使用dfs）
对深度优先搜索进一步理解。

class Solution(object):
    def dfs(self, start, end):
        if start > end:
            return [None]
        ans = []
        for val in range(start, end + 1):
            leftTree = self.dfs(start, val - 1)
            rightTree = self.dfs(val + 1, end)
            for l in leftTree:
                for r in rightTree:
                    root = TreeNode(val)
                    root.left = l
                    root.right = r
                    ans.append(root)
        return ans

    def generateTrees(self, n):
        """
        :type n: int
        :rtype: List[TreeNode]
        """
        if n == 0:
            return []
        return self.dfs(1, n)

这种类型的题目还不是很熟练，需要进一步加强。

98、validate binary search

class Solution(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        res = []
        self.inOrderToArray(root, res)
        for i in range(1, len(res)):
            if res[i-1] >= res[i]:
                return False
        return True
        
    def inOrderToArray(self, node, array):
        if node:
            if node.left:
                self.inOrderToArray(node.left, array)
            array.append(node.val)
            if node.right:
                self.inOrderToArray(node.right, array)

上面需要注意的有：1、>= ,二叉树没有两个节点相等的情况。
2、树的中序遍历要熟练。

class Solution2:
    # @param root, a tree node
    # @return a boolean
    def isValidBST(self, root):
        return self.isValidBSTRecu(root, float("-inf"), float("inf"))

    def isValidBSTRecu(self, root, low, high):
        if root is None:
            return True

        return low < root.val and root.val < high \
               and self.isValidBSTRecu(root.left, low, root.val) \
               and self.isValidBSTRecu(root.right, root.val, high)
    ```
这个解法效率比较高。上面是DFS的思想，并不断更新最大值最小值。