LeetCode 中 Tree的DFS

树是典型的可以用dfs算法的数据结构。 DFS往往都伴随着递归。但是与上一篇博客不同，这里的递归函数往往是help函数，难度也增加了，需要仔细分析 1. Path Sum I 检查是否有从root到leaf的path 使得他们的和等于sum，很典型的利用递归的DFS算法： 2. Path Sum II找到所有符合上题条件的路径 典型的DFS+回溯(pop_back) 3. Flatten Binary Tree to Linked List 思路是把每一个节点的left child置为空，right child挂在左子树最右子树（preorder right child的前驱）后面，right child放左子树（pre order 的next节点）。递归考虑右子树。 4. Binary Tree Maximum Path Sum 这题稍有难度。 三种情况需要考虑：1.左子树路径加当前根节点。2。右子树路径加当前根节点。 前两种情况都是以当前根节点为起始点。 3.如果path是穿过当前根节点的，那就需要左右子树路径加当前节点 5. Sum root to Leaf Numbers 思路是从root一直加下去，如果当前节点是叶子节点那么加到结果中去，否则最左右子数继续加。 6. Unique Binary Search Trees Given n, how many structurally unique BST's (binary search trees) that store values 1...n?
定义Count[i] 为以[0,i]能产生的Unique Binary Tree的数目， 如果数组为空，毫无疑问，只有一种BST，即空树， Count[0] =1
如果数组仅有一个元素{1}，只有一种BST，单个节点 Count[1] = 1
如果数组有两个元素{1,2}， 那么有如下两种可能
1                       2
  \                    /
    2                1
Count[2] = Count[0] * Count[1]   (1为根的情况)
                  + Count[1] * Count[0]  (2为根的情况。
再看一遍三个元素的数组，可以发现BST的取值方式如下：
Count[3] = Count[0]*Count[2]  (1为根的情况)
               + Count[1]*Count[1]  (2为根的情况)
               + Count[2]*Count[0]  (3为根的情况)

所以，由此观察，可以得出Count的递推公式为Count[i] = ∑ Count[0...k] * [ k+1....i]     0<=k<i-1
问题至此划归为一维动态规划。当数组为 1，2，3，4，.. i，.. n时，基于以下原则的BST建树具有唯一性：以i为根节点的树，其左子树由[0, i-1]构成， 其右子树由[i+1, n]构成。
7. Unique Binary Search Tree II
思路和上题类似，先定root然后把各种可能的左右子树分别组合。 8. Construct Binary Tree from Preorder and Inorder Traversal
9. Construct Binary Tree From PostOrder and InOrder TRaversal