目錄

• 95. Unique Binary Search Trees II （important）

求解樹類型的題目冠蒋，主要需要把握一下幾個(gè)關(guān)鍵：
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.

是一個(gè)遞歸求解思路切心。f(4) = f(0)f(3) + f(1)f(2) + f(2)f(1) + f(3)f(0)。因?yàn)槿《ㄒ粋€(gè)頂節(jié)點(diǎn)，兩邊的數(shù)是固定的绽昏。但是總數(shù)加起來固定扬霜，并且每邊的排列組合可以遞歸求出。

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進(jìn)行求解（求個(gè)數(shù)一般使用遞歸而涉，若枚舉可考慮使用dfs）
對深度優(yōu)先搜索進(jìn)一步理解。

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)

這種類型的題目還不是很熟練联予，需要進(jìn)一步加強(qiáng)啼县。

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沸久、>= ,二叉樹沒有兩個(gè)節(jié)點(diǎn)相等的情況季眷。
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)
    ```
這個(gè)解法效率比較高子刮。上面是DFS的思想，并不斷更新最大值最小值窑睁。