tree 总结

1. tree的性质：

Maximum Depth of Binary Tree
Minimum Depth of Binary Tree
Balanced Binary Tree
Same Tree
Symmetric Tree


树的性质判断是树的数据结构比较基本的操作， 争取一遍bug free。
前3道考树的深度问题，可能会考使用非递归做法（用queue）
Maximum Depth of Binary Tree就是遇到空结点返回0， 递归返回左右子树里面最大的那个。
Minimum Depth of Binary Tree稍微复杂一些， 因为当左子树为空时候按照定义深度不为0 而应该是右边子树到底的深度。 所以要对左子树右子树是否为空做一个判断。
Balanced Binary Tree原理也是求深度， 但是他的返回类型是boolean 所以要建立一个helper函数如果不平衡就返回－1。
后两道考树的便利， 递归退出条件是这两道题最难的地方。
Same Tree就是对两棵树同时便利
Symmetric Tree与前一道题基本相同， 但是输入只有一个treenode 所以要建立一个helper函数 让node的左右子树作为两个node比较。

2. 树的遍历

Binary Tree Preorder Traversal 中左右
Binary Tree Inorder Traversal 左中右
Binary Tree Postorder Traversal 左右中

前三道题属于图的深度优先搜索问题

这三种遍历的递归方法 就是递归左右节点直到空为止。中在哪个位置就在哪个位置把root加入最后的结果。 例如：preoder的递归式就是先加入root然后递归左右子树。

对于迭代的解法就是用栈来实现， 前两题用一个栈来保存前驱的分支结点（相当于图的深度搜索的栈）， 然后用一个结点来记录当前结点就可以了。 preorder要在root入栈时候就加入res， inorder则递归完左子树再加入res

Binary Tree Level Order Traversal

Binary Tree Level Order Traversal II

Binary Tree Zigzag Level Order Traversal

这三道题属于树的层序遍历， 都是广度优先搜索

用queue来实现

3. 树的求和

Path Sum

Path Sum II

Binary Tree Maximum Path Sum


Sum Root to Leaf Numbers

树的题目基本都是用递归或者分治来解决，主要考虑两个问题：

1）如何把问题分治成子问题给左子树和右子树。

2）考虑结束条件是什么。

难点就是考虑递归结束的条件是什么。

path sum II 要保存所有节点 所有要递归的dfs遍历

b

4. 树的构造

Convert Sorted Array to Binary Search Tree leetcode


Convert Sorted List to Binary Search Tree

array本身就是有序的 只需要取中点作为根 然后递归的寻找左右子树

list无序， 如果每次都寻找中点， 复杂度很高。 所以用中序遍历的方法来构造树

Construct Binary Tree from Preorder and Inorder Traversal

Construct Binary Tree from Inorder and Postorder Traversal

这两道题完全相同 分别通过preorder 和 postorder确定root的值 然后在inorder里找到root的位置 然后递归查找。 比较巧妙的是用了hashmap来存贮inorder的root和index 这样可以在o（1）时间里找到root的位置。

Flatten Binary Tree to Linked List 
这道题可以用先序遍历来逐个点递归解 也可以用stack的非递归方法

5. 树的变换

Populating Next Right Pointers in Each Node

Populating Next Right Pointers in Each Node II