分享binary tree的recursion解题思路

Binary tree的题可以用recursive 和iterative 方法解决。我主要分享下如何用recursive方法解决binary tree 的问题。欢迎大家指正。

Binary tree recursive一般有top down 和bottom-up 两种。top down是从上往下用preorder做。一般查看树的形态（比如 same tree, symmetric tree)和求从根节点到子节点的path之类的题，可以首先考虑用pre-order来做。

preorder 题的模版大概是如下：

1. base case (if root == NULL)
2. update answer based on current node and its left, right node
3. top_down(root->left, left_params)            
4. top_down(root->right, right_params)

bottom up 是从下往上，先求叶子节点，然后再处理根节点。这个相当于post-order. 求整个树的depth, 有多少节点，可以选择bottom up.

bottom up 的模版一般是：

1. base case
2. left_ans = bottom_up(root->left)
3. right_ans = bottom_up(root->right)
4. update and return answers (在这里一般需要建立root 和left_ans, right_ans的关系）

下面是一些关于tree的pre-order和post-order的题。也希望大家能够补充更多的题。

Preorder
100    Same Tree
101    Symmetric Tree
111    Minimum Depth of Binary Tree
112    Path Sum
113    Path Sum II
437    Path Sum III
129    Sum Root to Leaf Numbers
298    Binary Tree Longest Consecutive Sequence
257    Binary Tree Paths

Postorder
104    Maximum Depth of Binary Tree
110    Balanced Binary Tree
124    Binary Tree Maximum Path Sum
222    Count Complete Tree Nodes
226    Invert Binary Tree
236    LCA
250    Count Univalue Subtrees
366    Find Leaves of Binary Tree
654    Maximum Binary Tree

感谢楼主整理！在做BT的题目时经常感觉recursive解法会比iterative容易很多，不知道在面试时会不会被要求用只能用iterative解呢？(之前刷bt都是两种解法都写，后面就偷懒了…)