中序遍历二叉树全过程图解

中序遍历图解

首先看下中序遍历的代码，其接受一个根结点root作为参数，判断根节点是否为nil，不为nil则先递归遍历左子树。

func traversal(root *TreeNode,res *[]int)  {
    if root == nil {return}

    traversal(root.Left,res)
    *res = append(*res,root.Val)
    traversal(root.Right,res)
}

我们把树根结点A传递给它，其左结点为B，右结点为C。

首先我们要检查root是否为nil，其不为nil，通过递归继续遍历左边的子树，将左子树传递给递归函数，该层递归函数的root为B，其左子树为D 右子树为E，判断root是否为nil，root不为nil，继续将该树的左子树向下递归，该层递归函数的root为D，左右子树都为nil，我们检查root是否为nil，root为D，不为nil，继续递归遍历D的左子树，其左子树为nil，所以该层递归函数的root为nil，满足递归结束条件，执行return退出该层递归函数。

递到此处时的运行栈如下图所示

此时的return会回到root为D的递归层，D的左子树已经遍历完毕，我们执行下一行语句append，
该语句会将root的数据域加入到结构列表res中，即访问到了D，如下图

按照顺序继续执行，接下来将使用递归遍历D的右子树，这里D的右子树为nil，所以我们传入的递归参数也为nil，检测到root为nil，我们退出该层递归函数，回到调用层D，该层的所有语句都执行完毕了。我们继续回到调用它的函数，即B层的 traversal(root.Left,res)语句处

继续执行后序语句，执行 *res = append(*res,root.Val)记录root的数据域，即访问B，再执行下一条语句
递归访问B的右子树，将E传递给它，判断root是否为nil，root为E，不为nil，递归调用E的左子树，左子树为nil，判断root是否为nil，为nil，退出该层

执行下一行，将E记录到结果中，继续遍历E的右子树，右子树为nil，直接退出该层递归函数，返回到了E的递归层，E这层也执行完毕了，返回到调用它的B层

随即B层也执行完了，返回到调用它的A层 ，在该层执行下一行代码，将A记录到结果中，继续遍历A的右子树，A的右子树为C，其不为nil，递归C的左子树F，F不为nil，递归F的左子树，F的左子树为nil，即传入的root为nil，满足递归结束条件，开始回归上层。

返回到调用它的F层，将F记录到结果中。遍历F的右子树，F的右子树也为nil，退出该层，到此F这层函数执行完毕，返回到调用F的递归层 C，下一行语句记录C

继续下一行语句，递归C的右子树G，判断该层递归的root是否为nil，当前root为G，不为nil，递归G的左子树，左子树为nil，满足递归结束条件，返回到调用它的G，输出G，递归G的右子树，右子树为nil
满足递归结束条件，返回到调用它的G，G这层函数结束，返回上层到C

C也运行完毕，返回上层到A，A也运行完毕，此该树递归结束，这样我们就得到了中序遍历序列

总结

再次回顾一下代码

func traversal(root *TreeNode,res *[]int)  {
    if root == nil {return}

    traversal(root.Left,res)
    *res = append(*res,root.Val)
    traversal(root.Right,res)
}

从我们的遍历全流程图解来看，不难理解，每个节点都是将其左子树全部递归遍历完后，才开始遍历其右子树的，如根节点A，是将其左子树BDE全部遍历完后，才开始遍历右子树的，注意思考递归栈哦，这样才能真正的理解。

中序遍历理解后，前序和后续遍历是一样的道理。这时一起看下后续遍历的代码：

func traversal(root *TreeNode,res *[]int)  {
    if root == nil {return}
    
    traversal(root.Left,res)
    traversal(root.Right,res)
     *res = append(*res,root.Val)
}

很多同学看到递归左右子树的那两行代码，很容易陷入误区，以为那两行是"同时"在执行，认为遍历完root的左节点后，立马遍历了其右节点，这种理解是非常不对的，实际是遍历完整个左子树后，经过归回到当前层，此时才会开始执行当前层的traversal(root.Right,res)语句去遍历右子树。

尤其是看到两条回溯语句写在同一行时会更容易误解，如力扣104. 二叉树的最大深度

/**
 * definition for a binary tree node.
 * type treenode struct {
 *     val int
 *     left *treenode
 *     right *treenode
 * }
 */
func max (a, b int) int {
    if a > b {
        return a
    }
    return b
}

// 递归
func maxdepth(root *treenode) int {
    if root == nil {
        return 0
    }
    return max(maxdepth(root.left), maxdepth(root.right)) + 1
}

实际最后一行代码是简化版，等价于如下代码

/**
 * definition for a binary tree node.
 * type treenode struct {
 *     val int
 *     left *treenode
 *     right *treenode
 * }
 */
func max (a, b int) int {
    if a > b {
        return a
    }
    return b
}

// 递归
func maxdepth(root *treenode) int {
    if root == nil {
        return 0
    }
    leftDepth := maxdepth(root.left) // 递归左子树的深度
    rightDepth := maxdepth(root.right) // 递归右子树的深度
    
    return max(leftDepth,rightDepth ) + 1 // 当前根节点到叶子节点的最大深度
}

此时再看此代码是不是好理解一些 ，它就是我们的后序遍历哇！将左子树全部遍历完后，才会开始遍历右子树，最后则是根节点，然后回到上层调用栈，直到所有接地那遍历完毕，递归函数执行完毕。

拓展：回归与回溯

这里就是一个简介，详细可见：LeetCode 257. 二叉树的所有路径（回溯详解）

前序遍历以及回溯的过程如图：

回溯和递归中回归的区别：
回溯：因为我们要把路径记录下来，需要回溯来回退一个路径再进入另一个路径。
回归：下层函数栈执行完成后，回归到上层函数栈来

实际上，回溯和回归都是伴随递归出现的，只是回溯比回归多了一个路径回退的操作。