第 7 关 | 算法的基础——递归和二叉树 2.白银挑战——理解二叉树的遍历

树的前中后序是递归的重要应用，也是后面大量高频算法问题的基础，我们这里就来好好研究一下

1. 深入理解前中后序遍历

深度优先遍历有前中后三种情况，大部分人看过之后就能写出来，很遗憾大部分人只是背下来的，稍微变换一下就废了。
我们再从二叉树的角度看递归，每次遇到递归，都按照前面说的四步来写，可以更好地写出正确的递归算法。通过二叉树可以非常方便的理解递归，递归只处理当前这一层和下一层之间的关系，并不关心下层和下下层之间的关系，这就像老子只管养好儿子，至于孙子怎么样，那是儿子的事，你也不能瞎掺合。具体来说，我们总结了四条行之有效的方法来分解递归：
●第一步：从小到大递推
●第二步：分情况讨论，明确结束条件
●第三步：组合出完整方法
●第四步：想验证，则从大到小画图推演
我们接下来就一步步看怎么做：
第一步：从小到大递推，分情况讨论
我们就以这个二叉树为例：

   3
   / 
  9  20
    /  
   15   7
 

我们先选一个最小的子树：

  20
    /  
   15   7
 

假如20为head，则此时前序访问顺序应该是：

void visti1(){
    list.add(root);//20被访问
    root.left; // 继续访问 15
    root.right; // 继续访问 7
}

然后再向上访问，看node(3)的情况:

void visit2(){
    list.add(root);//3被访问
    root.left;//继续访问，得到9
    root.right; //继续访问，得到20
  }

这里的20是一个子树的父节点，访问方式与上面的visit1()一样，所以我们可以直接合并到一起就是：

void visit2(){
    list.add(root);//3被访问
    root.left;//继续访问，得到9
    root.right; //继续访问，得到20
  }

这就是我们期待的递归方法。
第二步：分情况讨论，明确结束条件
上面有了递归的主体，但是这个递归什么时候结束呢？很明显应该是root=null的时候。一般来说链表和二叉树问题的终止条件都包含当前访问的元素为null。有些题目结束条件比较复杂，此时最好的方式就是先将所有可能的结束情况列举出来，然后整理一下就行了，这个我们后面在具体题目里再看。
第三步：组合出完整方法
到此为止，我们就能将完整代码写出来了，同时为了方便区分，我们将方法名换成preorder：

public void preorder(TreeNode root, List res) {
        if (root == null) {
            return;
        }
        res.add(root.val);
        preorder(root.left, res);
        preorder(root.right, res);
    }

第四步 从大到小 画图推演写完之后对不对呢？递归的方法是很难调试的，即使对的，你也可能晕，这里介绍一种简单有效的验证方法——调用过程图法。我们可以画个过程图看一下，因为是两个递归函数，如果比较复杂，我们可以少画几组。
递归的特征是“不撞南墙不回头”，一定是在执行到某个root=null了才开始返回，下图中的序号就是递归的完整过程：

从图中可以看到，当root的一个子树为null的时候还是会执行递归，进入之后发现root==null了，然后就开始返回。这里我们要特别注意res.add()的时机对不对，将其进入顺序依次写出来就是需要的结果。该过程明确之后再debug就容易很多，刚开始学习递归建议多画几次，熟悉之后就不必再画了。
前序遍历写出来之后，中序和后序遍历就不难理解了，中序是左中右，后序是左右中。代码如下：

public static void inOrderRecur(TreeNode head) {
    if (head == null) {
        return;
    }
    inOrderRecur(head.left);
    System.out.print(head.value + " ");
    inOrderRecur(head.right);
}

再看后序的：

public static void postOrderRecur(TreeNode head) {
    if (head == null) {
        return;
    }
    postOrderRecur(head.left);
    postOrderRecur(head.right);
    System.out.print(head.value + " ");
}

另外需要注意一点，面试，以及LeetCode里提供的方法可能不能直接用来递归，需要我们再创建一个方法，例如：
LeetCode144 二叉树前序遍历问题，此时给的函数preorderTraversal()就难以直接递归，我们可以自己再创建一个：

class Solution {
    public:
    void preorder(TreeNode *root, vector &res) {
        if (root == nullptr) {
            return;
        }
        res.push_back(root->val);
        preorder(root->left, res);
        preorder(root->right, res);
    }
    
    vector preorderTraversal(TreeNode *root) {
        vector res;
        preorder(root, res);
        return res;
    }
};

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List preorderTraversal(TreeNode root) {
        List res = new ArrayList();
        preorder(root,res);
        return res;
    }
    public void preorder(TreeNode root,List res){
        if(root == null){
            return;
        }
        res.add(root.val);
        preorder(root.left,res);
        preorder(root.right,res);
    }
}
 

class Solution:
    def preorderTraversal(self, root) :
        def preorder(root):
            if not root:
                return
            res.append(root.val)
            preorder(root.left)
            preorder(root.right)
 
        res = list()
        preorder(root)
        return res

2. 通关文牒

本关讲解了树的前中后序遍历的基本问题，难度不算大，看懂即过关，先热身，后面有大招等着你