LeetCode 中 Tree相关的Recursion

Tree是一个很重要的考点。其中recursion的题目占很大的比例。 在tree中， recursion往往和dfs相结合。 这里我们探讨一下那些用recursion解决的问题思路都很直观，代码比较容易写出来的题目。 注意相对应的iterative的题目也需要掌握。
1. Tree Pre-Order，InOrder,PostOrder遍历 这里首先给出中序遍历递归代码 iterative for InOrder Travesal iterative for InOrder Travesal with O(1) space (have parent ptr) Iterative for PreOrder Travesal
Iterative for PostOrder Travesal
2.Validate Binary Search Tree
递归检查左子树比root值小，又子树比root值大。 3. Recover Binary Search Tree
可以先用O（n）space 将树中序序列化，然后找出乱序的数字。这里要求O（1）的space 3.a 另一个利用iterative inorder的方法，不需要全局变量 以上方法都用到了extra space。下面的方法真正用到了O(1)space 4. Same Tree
recursion 算法非常简单： 这里再给出iterative的方法 5. Symmetric Tree
思路和上一道题差不多。 Iterative: 6. Construct Binary Tree from Preorder and Inorder Tree
分段递归 7. Construct Binary Tree from Postorder and Inorder Tree
分段递归 8.Convert Sorted Array to Binary Search Tree
比较简单，每次取中间的数作为root，递归对左右两边的子数组进行操作。 9.Convert Sorted linkedList to Binary Search Tree
这题比上题复杂。 如果按照上题的思路每一层都需要遍历一次list 需要O（NlogN）。 如果采用从底向上的方法构建，可以充分利用list不能随机访问的性质，达到O（n） 10. Maximum Depth of Binary Tree
非常简单，递归调用 11. Minimum Depth of Binary Tree
思路和上题一样，但是不同的是，空！=零的关系，因此不能照搬上题的答案。 12， Balanced Search Tree 左右子数都是balance的而且两者maximum 高度差不超过1。