二叉树的递归遍历

本篇将介绍前后中序的递归写法，一些同学可能会感觉很简单，其实不然，我们要通过简单题目把方法论确定下来，有了方法论，后面才能应付复杂的递归。

这里帮助大家确定下来递归算法的三个要素。每次写递归，都按照这三要素来写，可以保证大家写出正确的递归算法！

1. 确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
2. 确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
3. 确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。

前中后遍历模板

前序：

void traversal(TreeNode treeNode, List<Integer> list) {
    if (treeNode == null) {
        return;
    }
    list.add(treeNode.val);                // 中
    traversal(treeNode.left, list);        // 左
    traversal(treeNode.right, list);    // 右
}

中序：

void traversal(TreeNode treeNode, List<Integer> list) {
    if (treeNode == null) {
        return;
    }
    traversal(treeNode.left, list);        // 左
    list.add(treeNode.val);                // 中
    traversal(treeNode.right, list);    // 右
}

后序：

void traversal(TreeNode treeNode, List<Integer> list) {
    if (treeNode == null) {
        return;
    }
    traversal(treeNode.left, list);        // 左
    traversal(treeNode.right, list);    // 右
    list.add(treeNode.val);                // 中
}

对于N叉数递归法也思路也是一致的：

例如:

N叉树递归的前序遍历

 public Node preTraversal(Node root) {
   if (root == null) {
     return null;
   }
   // 输出结果
   res.add(root.val);
   // 递归遍历
   for (int i = 0; i < root.children.size(); i++) {
     preTraversal(root.children.get(i));
   }
   return root;
 }

N叉树递归的后序遍历

public Node postTraversal(Node root) {
    if (root == null) {
        return null;
    }
    // 递归遍历
    for (int i = 0; i < root.children.size(); i++) {
        postTraversal(root.children.get(i));
    }
    // 输出结果
    res.add(root.val);
    return root;
}