深入理解二叉树遍历：从递归代码到调用栈

二叉树遍历要解决的问题只有一个按照什么顺序处理当前节点、左子树和右子树。左右子树本身也是二叉树所以可以用同一个函数继续处理。这就是递归。前序、中序和后序并非三种不同思想只是访问当前节点的时机不同。一、遍历顺序由访问位置决定对于任意节点递归框架都是voidtraverse(TreeNoderoot){if(rootnull){return;}// 位置一traverse(root.left);// 位置二traverse(root.right);// 位置三}访问操作放在不同位置就形成三种遍历前序根 → 左 → 右 中序左 → 根 → 右 后序左 → 右 → 根对应代码如下// 前序遍历voidpreorder(TreeNoderoot,ListIntegerresult){if(rootnull){return;}result.add(root.value);preorder(root.left,result);preorder(root.right,result);}// 中序遍历voidinorder(TreeNoderoot,ListIntegerresult){if(rootnull){return;}inorder(root.left,result);result.add(root.value);inorder(root.right,result);}// 后序遍历voidpostorder(TreeNoderoot,ListIntegerresult){if(rootnull){return;}postorder(root.left,result);postorder(root.right,result);result.add(root.value);}所以“前、中、后”描述的是根节点相对于左右子树的访问位置进入节点时访问 → 前序 左子树处理完后访问 → 中序 左右子树都处理完后访问 → 后序二、调用栈如何产生遍历顺序重点理解栈存储的是调用位置。梳理清楚前、中、后遍历时各元素是如何压栈的。使用下面的二叉树1 / \ 2 3 / \ / \ 4 5 6 7递归调用时每进入一个节点就把该节点的函数压入调用栈。子函数执行期间父函数暂停子函数返回后父函数从暂停位置继续。需要区分压栈进入函数 访问处理节点 出栈函数执行完毕访问节点不等于函数出栈。1. 前序遍历前序遍历进入节点后立即访问因此压栈路径直接形成访问顺序。进入并访问 1 栈顶 ┌──────────────┐ │ 1等待左子树 │ └──────────────┘ 栈底 输出1进入并访问 2 栈顶 ┌──────────────┐ │ 2等待左子树 │ ├──────────────┤ │ 1等待左子树 │ └──────────────┘ 栈底 输出1 2进入并访问 4 栈顶 ┌──────────────┐ │ 4正在执行 │ ├──────────────┤ │ 2等待左子树 │ ├──────────────┤ │ 1等待左子树 │ └──────────────┘ 栈底 输出1 2 44完成后出栈再进入52完成后出栈再进入3、6、7。完整访问顺序 1 → 2 → 4 → 5 → 3 → 6 → 72. 中序遍历中序遍历先进入左子树因此开始时只压栈不访问。依次进入 1、2、4 栈顶 ┌──────────────┐ │ 4等待左子树 │ ├──────────────┤ │ 2等待左子树 │ ├──────────────┤ │ 1等待左子树 │ └──────────────┘ 栈底 输出空4的左子树为空所以访问4并返回。随后恢复2访问2再进入右子树5。栈顶 ┌──────────────┐ │ 5正在执行 │ ├──────────────┤ │ 2等待右子树 │ ├──────────────┤ │ 1等待左子树 │ └──────────────┘ 栈底 输出4 → 25完成后2才能出栈。随后访问1再以相同方式处理右子树。完整访问顺序 4 → 2 → 5 → 1 → 6 → 3 → 7中序遍历的栈中保存的是左子树尚未完成或者右子树尚未处理的节点。3. 后序遍历后序遍历必须等左右子树都完成后才能访问当前节点。依次进入 1、2、4 栈顶 ┌──────────────┐ │ 4等待子树 │ ├──────────────┤ │ 2等待左子树 │ ├──────────────┤ │ 1等待左子树 │ └──────────────┘ 栈底 输出空4没有子树因此访问并出栈。接着进入并访问5。此时2的左右子树都已完成才访问2。栈顶 ┌────────────────┐ │ 2左右均已完成 │ ├────────────────┤ │ 1等待左子树 │ └────────────────┘ 栈底 输出4 → 5 → 2右子树同理依次访问6、7、3。最后节点1的左右子树都完成访问1。完整访问顺序 4 → 5 → 2 → 6 → 7 → 3 → 1后序遍历体现的是依赖关系必须先得到左右子树的结果才能处理当前节点。三、完整实现与复杂度importjava.util.ArrayList;importjava.util.List;publicclassBinaryTreeTraversal{staticclassTreeNode{intvalue;TreeNodeleft;TreeNoderight;TreeNode(intvalue){this.valuevalue;}}// 前序根 - 左 - 右staticvoidpreorder(TreeNoderoot,ListIntegerresult){if(rootnull){return;}result.add(root.value);preorder(root.left,result);preorder(root.right,result);}// 中序左 - 根 - 右staticvoidinorder(TreeNoderoot,ListIntegerresult){if(rootnull){return;}inorder(root.left,result);result.add(root.value);inorder(root.right,result);}// 后序左 - 右 - 根staticvoidpostorder(TreeNoderoot,ListIntegerresult){if(rootnull){return;}postorder(root.left,result);postorder(root.right,result);result.add(root.value);}publicstaticvoidmain(String[]args){/* * 1 * / \ * 2 3 * / \ / \ * 4 5 6 7 */TreeNoderootnewTreeNode(1);root.leftnewTreeNode(2);root.rightnewTreeNode(3);root.left.leftnewTreeNode(4);root.left.rightnewTreeNode(5);root.right.leftnewTreeNode(6);root.right.rightnewTreeNode(7);ListIntegerpreorderResultnewArrayList();ListIntegerinorderResultnewArrayList();ListIntegerpostorderResultnewArrayList();preorder(root,preorderResult);inorder(root,inorderResult);postorder(root,postorderResult);System.out.println(前序遍历preorderResult);System.out.println(中序遍历inorderResult);System.out.println(后序遍历postorderResult);}}输出前序遍历[1, 2, 4, 5, 3, 6, 7] 中序遍历[4, 2, 5, 1, 6, 3, 7] 后序遍历[4, 5, 2, 6, 7, 3, 1]每个节点只被处理一次因此时间复杂度O(n) 空间复杂度O(h)其中n是节点数量h是树高。空间消耗来自递归调用栈。最终可以将三种遍历统一为一句话递归负责处理左右子树访问根节点的位置决定遍历类型访问在左递归之前是前序在左右递归之间是中序在右递归之后是后序。