二叉树中序遍历-递归法详解-数据结构与算法
首先看下中序遍历的代码：（左 跟 右）
其首先要接受一个根结点root作为参数 判断根节点是否为NULL 不为NULL则递归遍历左子树
①我们把树根结点A传递给它 其左结点为B，右结点为C
②首先我们要检查root是否为NULL 其不为NULL 通过递归继续遍历左边的子树
将左子树传递给递归函数 该层递归函数的root为B 其左子树为D 右子树为E
③判断root是否为NULL root不为NULL 继续将该树的左子树向下递
该层递归函数的root为D 左右子树都为NULL 我们检查root是否为NULL root为D，不为NULL
④继续递归遍历D的左子树 其左子树为NULL 所以该层递归函数的root为null 满足递归结束条件 执行return退出该层递归函数 ，则回到root为D的递归层 D的左子树已经遍历完毕 我们执行下一行语句print 该语句会输出该root的数据域（root.val），即访问到了D
⑤按照顺序继续执行，接下来将使用递归遍历D的右子树 这里D的右子树为NULL 所以我们传入的递归参数也为NULL 检测到root为NULL，我们退出该层递归函数
⑥回到调用层D，该层的所有语句都执行完毕了 我们继续回到调用它的函数 这层的root为B 继续执行后序语句 输出root的数据域，即访问B
⑦执行下一条语句 递归访问它的右子树 将E传递给它 判断root是否为NULL root为E，不为NULL
⑧递归调用E的左子树，左子树为NULL 判断root是否为NULL 为NULL 退出该层 执行下一行 输出E
⑨继续遍历E的右子树 右子树为NULL 直接退出该层递归函数，返回到了E的递归层
⑩E这层也执行完毕了，返回到调用它的B层 B层也执行完了 返回到调用它的A层
⑪在该层执行下一行代码 输出A 继续遍历A的右子树 A的右子树为C 其不为NULL 递归C的左子树F
⑫F不为NULL 递归F的左子树 F的左子树为NULL 即传入的root为NULL 满足递归结束条件，返回到调用它的F层 输出F
⑬遍历F的右子树 F的右子树也为NULL 退出该层 到此F这层函数执行完毕，返回到调用F的递归层 C 输出C
⑭递归C的右子树G 判断该层递归的root是否为NULL 当前root为G，不为NULL 递归G的左子树 左子树为NULL 满足递归结束条件，返回到调用它的G 输出G
⑮递归G的右子树 右子树为NULL 满足递归结束条件，返回到调用它的G G这层函数结束，返回上层到C
⑯C也运行完毕，返回上层到A A也运行完毕
到此该树递归结束，这样我们就得到了中序遍历序列
【D B E A F C G】
其他遍历顺序也类似的过程。
//Java版本的中序递归遍历参考代码：
class Solution {public List<Integer> inorderTraversal(TreeNode root) {//定义一个 整数型的集合，用于存放遍历的结果数组List<Integer> result = new ArrayList<>();inorder(root,result);return result;}//中序遍历public void inorder(TreeNode root,List<Integer> result){//递归终止条件if(root == null) return;inorder(root.left,result); //左result.add(root.val); //中inorder(root.right,result); //右}
}