教程【免费下载链接】Learn-Algorithms算法学习笔记项目地址https://gitcode.com/gh_mirrors/le/Learn-Algorithms点击查看免费下载本篇技术指南聚焦 Learn-Algorithms 仓库「9 Algorithms Job Interview」目录下的「7.1 二叉树-遍历」专题系统梳理二叉树遍历在算法面试中的核心考点先序/中序/后序遍历的递归与非递归两种实现方式、按层打印二叉树、二叉树的最大深度与最小深度、完全二叉树节点个数以及“判断整数序列是否为二元查找树的后序遍历结果”这一经典辨析题。读完本文你将掌握二叉树的统一递归遍历框架、借助栈实现非递归遍历、借助队列实现层次遍历的完整套路并能独立推导出树的深度类问题与后序遍历序列判定问题的解法与复杂度分析。从一道引子说起快排是前序遍历归并是后序遍历文档开篇引用了算法学习中一个非常经典的观点快速排序就是个二叉树的前序遍历归并排序就是个二叉树的后序遍历这句话想表达的是很多看似与树无关的算法其递归结构在本质上与二叉树的遍历是同构的。在「9 Algorithms Job Interview/README.md」的刷题框架中作者把排序算法与二叉树遍历框架直接对照展示# 快排 quickSort —— 前序遍历位置 void quicksort(int[] nums, int left, int right){ if (left right) { // 递归结束条件 // 前序遍历位置先划分使得局部有序 int i partion(nums, left, right); quicksort(nums, left, i-1); // 处理左区间 quicksort(nums, i1, right); // 处理右区间 } } # 归并排序 mergeSort —— 后序遍历位置 void mergeSort(int[] nums, int low, int high){ int mid (low high) / 2; sort(nums, low, mid); sort(nums, mid 1, high); /****** 后序遍历位置 ******/ // 合并两个排好序的子数组 merge(nums, low, mid, high); /************************/ }快排先通过partition确定 pivot 的位置相当于“处理当前节点”再递归处理左右区间对应二叉树的前序遍历根 → 左 → 右归并排序先递归排序左右两半最后在返回途中合并相当于“处理完左右子树再处理当前节点”对应二叉树的后序遍历左 → 右 → 根。理解这层对应关系有助于在写递归算法时找准“当前节点该做什么、什么时候做”。递归框架二叉树算法的统一底座在「7 二叉树.md」中作者给出了二叉树算法的核心心法写二叉树的算法题都是基于递归框架的。我们先要搞清楚 root 节点它自己要做什么然后根据题目要求选择使用前序中序后序的递归框架。二叉树结点定义C 风格struct SBinaryTreeNode // a node of the binary tree { int m_nValue; // value of node SBinaryTreeNode *m_pLeft; // left child of node SBinaryTreeNode *m_pRight; // right child of node };统一递归遍历框架Java 伪码/* 二叉树遍历框架 */ void traverse(TreeNode root) { // 前序遍历位置在这里访问 root traverse(root.left); // 中序遍历位置在这里访问 root traverse(root.right); // 后序遍历位置在这里访问 root }在这个框架里“访问当前节点”的代码写在哪个位置就决定了它是前序、中序还是后序遍历。所有基于递归的二叉树算法题遍历、翻转、求深度、求路径、判子树等都可以套用这个框架只需在合适的位置插入具体逻辑。2 种方法实现二叉树的前序遍历递归与非递归文档要求用递归和非递归两种方法实现前序遍历下面以仓库源码为参照逐一给出完整实现。方法一递归实现仓库「4 Tree/1-二叉树 /btree/bintree.c」给出了可直接编译运行的 C 实现int PreOrderTraverse(BiTree T){ if (T) { printf(%c\n, T-item); // 先访问根结点 PreOrderTraverse(T-lChild); // 再遍历左子树 PreOrderTraverse(T-rChild); // 最后遍历右子树 } return 0; }同一份源码中还配套实现了中序与后序的递归版本三者的差别仅仅是printf语句的位置// 中序遍历左子树 → 根 → 右子树 int InOrderTraverse(BiTree T){ if (T) { InOrderTraverse(T-lChild); printf(%c\n, T-item); InOrderTraverse(T-rChild); } return 0; } // 后序遍历左子树 → 右子树 → 根 int PostOrderTraverse(BiTree T){ if (T) { PostOrderTraverse(T-lChild); PostOrderTraverse(T-rChild); printf(%c\n, T-item); } return 0; }递归实现的本质系统调用栈替我们保存了“访问完左子树后该回到哪个节点”的信息。时间复杂度 O(n)每个节点恰好访问一次空间复杂度为递归栈深度 O(h)h 为树高最坏情况下退化成链为 O(n)。方法二非递归显式栈实现非递归前序遍历的核心是用显式栈模拟系统调用栈。套路如下先将根结点入栈循环弹出栈顶节点并访问由于前序要求“先左后右”而栈是后进先出所以先压右孩子、再压左孩子栈空则遍历结束。// 非递归前序遍历 void preOrderIterative(BiTree T){ if (!T) return; Stack stack; // 显式栈元素类型为 BiTree initStack(stack); push(stack, T); while (!isEmptyStack(stack)) { BiTree node pop(stack); printf(%c\n, node-item); // 访问当前节点 if (node-rChild) push(stack, node-rChild); // 先压右 if (node-lChild) push(stack, node-lChild); // 后压左保证左先出栈 } }同理可推广出非递归的中序与后序中序需“沿左链一路入栈、弹出时访问并转向右子树”后序可借助两个栈或“根右左”的逆序输出面试中先掌握前序的非递归写法即可触类旁通。按层打印二叉树层序遍历题目输入一棵二元树从上往下按层打印树的每个结点同一层中按照从左往右的顺序打印。例如输入8 /\ 6 10 / \ /\ 5 7 9 11输出8 6 10 5 7 9 11。解法辅助队列BFS这正是二叉树的层序遍历广度优先遍历核心数据结构是队列根结点入队之后每次从队头取出一个节点打印并将其左、右孩子依次入队直到队列为空。仓库「4 Tree/1-二叉树 /btree/bintree.c」给出了配套的完整 C 实现含自定义链式队列Queue及其initQueue/enQueue/deQueue/isEmpty等操作// 广度优先遍历队列实现 int LevelOrderTraverse(BiTree T){ if (T) { Queue queue; initQueue(queue); BiTree u; u (BiTree)malloc(sizeof(BiTNode)); enQueue(queue, T); // 根结点入队 while (!isEmpty(queue)) { deQueue(queue, u); // 队头出队 printf(%c, u-item); // 访问当前节点 if (u-lChild) enQueue(queue, u-lChild); // 左孩子入队 if (u-rChild) enQueue(queue, u-rChild); // 右孩子入队 } } return 0; }算法流程根结点入队队非空时循环出队队头节点并打印将该节点的左孩子若非空入队再将右孩子若非空入队队列为空时结束此时恰好按“从上到下、从左到右”的顺序输出全部节点。复杂度分析每个节点入队、出队各一次时间复杂度 O(n)辅助队列最多同时容纳一层节点空间复杂度 O(w)w 为树的最大宽度最坏 O(n)。补充剑指offer专题见「9 Algorithms Job Interview/剑指offer/README.md」中“从上往下打印二叉树”一题即此问题标记的解题思路就是“辅助队列”接口为void print_binary_level(BinaryTreeNode *root)。二元树的深度最大深度题目输入一棵二元树的根结点求该树的深度。从根结点到叶结点依次经过的结点含根、叶结点形成树的一条路径最长路径的长度为树的深度。例如输入10 / \ 6 14 / / \ 4 12 16输出该树的深度 3。解法后序遍历框架树的深度天然是一个“自底向上汇总”的问题某个节点的深度 max(左子树深度, 右子树深度) 1。因此它对应后序遍历框架——先递归求出左右子树的深度再在“后序遍历位置”汇总。这正是仓库「9 Algorithms Job Interview/剑指offer/README.md」中“二叉树的深度”一题的思路标记递归接口为int tree_depth(BTree *root)。int treeDepth(BiTree T){ if (T NULL) return 0; // 空树深度为 0 int leftDepth treeDepth(T-lChild); // 递归求左子树深度 int rightDepth treeDepth(T-rChild); // 递归求右子树深度 return (leftDepth rightDepth ? leftDepth : rightDepth) 1; // 后序位置汇总 }复杂度分析每个节点访问一次时间复杂度 O(n)递归栈深度等于树高空间复杂度 O(h)。变种同层节点 pNext 指针分析题文档在深度题之后附带了一道延伸分析对一棵完全二叉树要求给所有节点加上一个pNext指针指向同一层的相邻节点若当前节点已是该层最后一个节点则pNext指向 NULL并分析时间、空间复杂度。解题要点本质仍是层序遍历但在出队时同时记录“本层节点数”从而知道每层的边界做法BFS 过程中维护levelSize当前层节点数每出队一个节点就把pNext指向队头即同层下一个节点当处理完levelSize个节点时把最后一个节点的pNext置 NULL并重置levelSize为下一层实际入队节点数时间复杂度 O(n)空间复杂度 O(w)w 为最大层宽。二元树的最小深度题目输入一棵二元树的根结点求最小深度。例如输入10 / \ 6 14 / \ 12 16输出该树的最小深度 2。注意最小深度是根结点到最近叶子结点的最短路径上的节点数与最大深度看似对称但有一个关键陷阱——不能简单把max换成min。当某个节点只有左子树或只有右子树时缺失的一侧深度为 0如果直接取min(0, 右子树深度) 1会把“没有子树的一侧”误算成深度 1得到错误答案。正确写法int minDepth(BiTree T){ if (T NULL) return 0; // 叶子节点左右子树都为空 if (T-lChild NULL T-rChild NULL) return 1; if (T-lChild NULL) return minDepth(T-rChild) 1; // 只有右子树 if (T-rChild NULL) return minDepth(T-lChild) 1; // 只有左子树 // 左右子树都存在取较小者 return (minDepth(T-lChild) minDepth(T-rChild) ? minDepth(T-lChild) : minDepth(T-rChild)) 1; }复杂度分析最坏情况下每个节点访问一次时间复杂度 O(n)空间复杂度 O(h)。完全二叉树的节点个数求一棵完全二叉树的节点总数要求尽量优于朴素的 O(n) 全遍历。利用完全二叉树的性质可以做到O(log²n)若一棵树是满二叉树左右子树高度相等节点数直接等于2^h - 1无需继续下探否则递归统计count 1 count(left) count(right)并且每次递归时总有一棵子树是满二叉树可以直接套公式判断左右子树高度是否相等需要沿最左链/最右链数深度每次 O(log n)而递归深度也是 O(log n)故总复杂度 O(log²n)。int countNodes(BiTree T){ if (T NULL) return 0; // 沿最左链、最右链分别计算深度 int lh 0, rh 0; BiTree p T; while (p) { lh; p p-lChild; } p T; while (p) { rh; p p-rChild; } if (lh rh) return (1 lh) - 1; // 满二叉树2^h - 1 return 1 countNodes(T-lChild) countNodes(T-rChild); }该解法是“遍历 性质利用”的典型结合也是面试中常见的优化追问点。判断整数序列是不是二元查找树的后序遍历结果题目输入一个整数数组判断该数组是不是某**二元查找树BST**的后序遍历的结果。如果是返回 true否则返回 false。例如输入5、7、6、9、11、10、8由于这一整数序列是如下树的后序遍历结果8 / \ 6 10 /\ / \ 5 7 9 11因此返回 true。如果输入7、4、6、5则没有哪棵树的后序遍历结果等于该序列返回 false。思路利用 BST 性质 后序序列的递归结构后序遍历的序列天然满足“左子树 | 右子树 | 根”三段式结构而二元查找树要求左子树所有节点 根 右子树所有节点。据此可以递归判定序列最后一个元素是根结点root从序列头部开始找到第一个大于root的位置它把序列切成左子树区间和右子树区间校验右子树区间内所有元素都必须大于root否则不可能是 BST 的后序遍历递归对左右子树区间做同样的判定区间为空或只剩一个元素时返回 true。// data[l..r) 是否为某 BST 的后序遍历 bool verifyPostOrder(int *data, int l, int r){ if (data NULL || r - l 1) return true; // 空区间或单元素 int root data[r - 1]; // 最后一个元素是根 int i l; while (i r - 1 data[i] root) i; // 左子树区间都小于 root int j i; while (j r - 1) { if (data[j] root) return false; // 右子树区间出现小于根的节点 → 非法 j; } // 递归判定左、右子树区间 return verifyPostOrder(data, l, i) verifyPostOrder(data, i, r - 1); }对示例5、7、6、9、11、10、8根为 8左子树区间5,7,6均 8右子树区间9,11,10均 8再递归判定5,7,6根 6左 5、右 7与9,11,10根 10左 9、右 11全部满足返回 true。而7、4、6、5根为 5第一个大于 5 的元素是 7右子树区间4,6中出现4 5立即返回 false。该题在「9 Algorithms Job Interview/剑指offer/README.md」中对应“二叉搜索树的后序遍历序列”解题标记为“寻找规律”接口为bool is_post_order(BST *root, int *data, int length)。复杂度分析最坏情况树退化为链下每层都要扫描区间时间复杂度 O(n²)平均情况 O(n log n)。空间复杂度 O(h)递归栈。小结二叉树遍历类面试题的通用套路结合「9 Algorithms Job Interview/7 二叉树.md」与本文题目可以把二叉树遍历类问题收敛为一套方法论题目类型核心框架关键数据结构复杂度时间/空间前/中/后序遍历递归统一遍历框架按位置插入访问逻辑系统栈O(n) / O(h)前序遍历非递归显式栈模拟先压右再压左栈O(n) / O(h)按层打印层序遍历队列 BFS出队访问、孩子入队队列O(n) / O(w)最大深度后序框架max(左,右)1递归O(n) / O(h)最小深度后序框架注意单子树陷阱递归O(n) / O(h)完全二叉树节点数满二叉树公式 2^h-1 递归递归O(log²n) / O(log n)判断 BST 后序序列三段式结构 BST 大小关系递归划分递归O(n²) 最坏 / O(h)面试中拿到二叉树题目先问自己三件事当前节点要做什么放在前/中/后哪个位置做是否需要用队列/栈显式控制访问顺序想清楚这三步即可快速套用递归框架或非递归模拟写出正确代码。如需继续深入可进一步阅读仓库中的「7 二叉树.md」翻转、子树、最近公共祖先、和为某值的路径等同类递归题、「9 Algorithms Job Interview/README.md」遍历/递归/排序等刷题框架汇总以及「4 Tree/1-二叉树 /btree/bintree.c」前中后层四种遍历的完整可编译 C 实现。赞分享教程【免费下载链接】Learn-Algorithms算法学习笔记项目地址https://gitcode.com/gh_mirrors/le/Learn-Algorithms点击查看免费下载相关推荐二叉树层序遍历终极指南队列与递归两种实现的深度解析 二叉树层序遍历终极指南队列与递归两种实现的深度解析 二叉树的层序遍历Level Order Traversal是算法学习中的核心知识点也是Leet示例工程教程LeetCode 102 二叉树的层序遍历队列分层标记与递归实现全解析leetcode 题解LeetCode 102 二叉树的层序遍历队列分层标记与递归实现全解析leetcode 题解 本文基于 leetcode 题解仓库中的 102. 二叉树的文档教程知识库Hello 算法中的二叉树深度优先遍历前序、中序、后序遍历的递归实现与可视化调试Hello 算法中的二叉树深度优先遍历前序、中序、后序遍历的递归实现与可视化调试 二叉树遍历是树结构学习的基石。树的物理结构基于链表、逻辑结构却是非线性的这教程文档示例工程教育上一篇A2UI示例项目解析学习实战中的最佳实践下一篇Amazon Kiro 与 CodeRunner 集成打造安全的 AI 开发工作流创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
