概述学完 DFS 和 BFS 之后我们进入第三阶段树结构与经典策略。树是一种非常重要的数据结构。它不像数组、链表那样是简单的线性结构而是一种天然的层级结构。很多现实问题都可以抽象成树文件目录公司组织架构网页 DOM 结构表达式语法树搜索决策树在算法题中最常见的是二叉树。二叉树题经常考察前序遍历中序遍历后序遍历层序遍历最大深度路径问题二叉搜索树这些题看起来很多但基础都离不开一个核心能力遍历一棵树这篇文章会从树的基本概念讲起重点掌握二叉树的递归和迭代遍历写法。学完这篇你应该能看懂二叉树结构并能独立写出前序、中序、后序和层序遍历。核心概念树到底是什么树是一种由节点和边组成的数据结构。一棵树通常长这样1 / \ 2 3 / \ 4 5其中1是根节点2和3是1的子节点1是2和3的父节点4和5是叶子节点从1到4的路径是1 - 2 - 4树有一个非常重要的特点除了根节点每个节点都有且只有一个父节点常见术语术语含义根节点树最上面的节点父节点当前节点的上一层节点子节点当前节点的下一层节点叶子节点没有子节点的节点深度从根节点到当前节点经过的层数高度从当前节点到最远叶子节点的距离子树以某个节点为根形成的一棵树什么是二叉树二叉树是最常见的一类树。它的定义是每个节点最多有两个子节点这两个子节点通常叫左子节点右子节点Java 中常见的二叉树节点定义如下publicclassTreeNode{intval;TreeNodeleft;TreeNoderight;TreeNode(){}TreeNode(intval){this.valval;}TreeNode(intval,TreeNodeleft,TreeNoderight){this.valval;this.leftleft;this.rightright;}}二叉树的每个节点最多有左右两个孩子很多题都可以转化为“当前节点、左子树、右子树”之间的关系。递归思维为什么树天然适合递归树结构天然适合递归。因为一棵二叉树可以拆成根节点 左子树 右子树而左子树和右子树本身又是二叉树。这和递归思想完全一致大问题 当前节点要做的事 左子树问题 右子树问题所以二叉树题常见递归模板是voiddfs(TreeNoderoot){if(rootnull){return;}// 处理当前节点dfs(root.left);dfs(root.right);}递归终止条件树递归中最常见的终止条件是if(rootnull){return;}因为null表示空树。当递归走到空节点时就不需要继续往下走了。二叉树题通常只需要想清楚当前节点怎么处理剩下交给左右子树递归完成。前序遍历根、左、右前序遍历的顺序是根节点 - 左子树 - 右子树对于下面这棵树1 / \ 2 3 / \ 4 5前序遍历结果是1, 2, 4, 5, 3递归写法importjava.util.ArrayList;importjava.util.List;classSolution{publicListIntegerpreorderTraversal(TreeNoderoot){ListIntegeransnewArrayList();preorder(root,ans);returnans;}privatevoidpreorder(TreeNoderoot,ListIntegerans){if(rootnull){return;}ans.add(root.val);preorder(root.left,ans);preorder(root.right,ans);}}执行过程前序遍历先处理当前节点再递归左子树最后递归右子树。访问 1 访问 2 访问 4 访问 5 访问 3适用场景前序遍历常用于复制一棵树序列化二叉树先处理父节点再处理子节点的问题前序遍历的特点是先访问根节点再访问左右子树。中序遍历左、根、右中序遍历的顺序是左子树 - 根节点 - 右子树对于这棵树1 / \ 2 3 / \ 4 5中序遍历结果是4, 2, 5, 1, 3递归写法importjava.util.ArrayList;importjava.util.List;classSolution{publicListIntegerinorderTraversal(TreeNoderoot){ListIntegeransnewArrayList();inorder(root,ans);returnans;}privatevoidinorder(TreeNoderoot,ListIntegerans){if(rootnull){return;}inorder(root.left,ans);ans.add(root.val);inorder(root.right,ans);}}中序遍历和二叉搜索树中序遍历在二叉搜索树中非常重要。二叉搜索树的性质是左子树所有节点值 根节点值 右子树所有节点值因此对二叉搜索树进行中序遍历会得到一个升序序列。例如4 / \ 2 6 / \ / \ 1 3 5 7中序遍历结果是1, 2, 3, 4, 5, 6, 7中序遍历在普通二叉树中是一种遍历顺序在二叉搜索树中常用来得到有序结果。后序遍历左、右、根后序遍历的顺序是左子树 - 右子树 - 根节点对于这棵树1 / \ 2 3 / \ 4 5后序遍历结果是4, 5, 2, 3, 1递归写法importjava.util.ArrayList;importjava.util.List;classSolution{publicListIntegerpostorderTraversal(TreeNoderoot){ListIntegeransnewArrayList();postorder(root,ans);returnans;}privatevoidpostorder(TreeNoderoot,ListIntegerans){if(rootnull){return;}postorder(root.left,ans);postorder(root.right,ans);ans.add(root.val);}}适用场景后序遍历常用于删除一棵树计算子树信息求二叉树最大深度判断平衡二叉树路径和、树形 DP因为后序遍历是先处理左右子树再处理当前节点。所以当当前节点的答案依赖子树结果时后序遍历非常合适。后序遍历适合先拿到左右子树结果再汇总当前节点答案的问题。三种深度优先遍历对比前序、中序、后序都属于 DFS。它们的区别只在于根节点在什么时候被访问遍历方式顺序根节点位置典型用途前序遍历根、左、右最前面复制树、序列化中序遍历左、根、右中间二叉搜索树有序输出后序遍历左、右、根最后面计算子树信息可以记成前中后说的是根节点的位置前序遍历的迭代写法递归遍历本质上使用的是系统调用栈。我们也可以自己用栈来模拟递归。前序遍历顺序是根 - 左 - 右由于栈是后进先出所以入栈时要先放右节点再放左节点。Java 代码实现importjava.util.ArrayList;importjava.util.List;importjava.util.Stack;classSolution{publicListIntegerpreorderTraversal(TreeNoderoot){ListIntegeransnewArrayList();if(rootnull){returnans;}StackTreeNodestacknewStack();stack.push(root);while(!stack.isEmpty()){TreeNodenodestack.pop();ans.add(node.val);if(node.right!null){stack.push(node.right);}if(node.left!null){stack.push(node.left);}}returnans;}}为什么先压右节点栈的特点是后进先出。如果希望左节点先被访问就要让左节点后入栈。所以顺序是先压右节点再压左节点这样弹出时就是左节点先出右节点后出中序遍历的迭代写法中序遍历的顺序是左 - 根 - 右迭代写法需要不断把左链压入栈中。Java 代码实现importjava.util.ArrayList;importjava.util.List;importjava.util.Stack;classSolution{publicListIntegerinorderTraversal(TreeNoderoot){ListIntegeransnewArrayList();StackTreeNodestacknewStack();TreeNodecurroot;while(cur!null||!stack.isEmpty()){while(cur!null){stack.push(cur);curcur.left;}curstack.pop();ans.add(cur.val);curcur.right;}returnans;}}代码怎么理解中序遍历要先访问最左边的节点。所以代码先一路向左while(cur!null){stack.push(cur);curcur.left;}当左边走不动了再弹出栈顶节点访问。访问完当前节点后再转向右子树curcur.right;中序迭代的核心是先把左链全部压栈再依次弹出并转向右子树。后序遍历的迭代写法后序遍历顺序是左 - 右 - 根它的迭代写法比前序和中序稍微复杂。一种比较容易理解的方法是先得到 根 - 右 - 左 再反转成 左 - 右 - 根Java 代码实现importjava.util.ArrayList;importjava.util.Collections;importjava.util.List;importjava.util.Stack;classSolution{publicListIntegerpostorderTraversal(TreeNoderoot){ListIntegeransnewArrayList();if(rootnull){returnans;}StackTreeNodestacknewStack();stack.push(root);while(!stack.isEmpty()){TreeNodenodestack.pop();ans.add(node.val);if(node.left!null){stack.push(node.left);}if(node.right!null){stack.push(node.right);}}Collections.reverse(ans);returnans;}}为什么这样能得到后序上面的遍历过程访问顺序是根 - 右 - 左把它反转后就得到左 - 右 - 根也就是后序遍历。这种写法不是最节省操作的写法但非常适合初学者理解。层序遍历一层一层访问节点前序、中序、后序都是 DFS。层序遍历则是 BFS。层序遍历的顺序是从上到下从左到右一层一层访问节点对于这棵树1 / \ 2 3 / \ 4 5层序遍历结果是[ [1], [2, 3], [4, 5] ]Java 代码实现importjava.util.ArrayList;importjava.util.LinkedList;importjava.util.List;importjava.util.Queue;classSolution{publicListListIntegerlevelOrder(TreeNoderoot){ListListIntegeransnewArrayList();if(rootnull){returnans;}QueueTreeNodequeuenewLinkedList();queue.offer(root);while(!queue.isEmpty()){intsizequeue.size();ListIntegerlevelnewArrayList();for(inti0;isize;i){TreeNodenodequeue.poll();level.add(node.val);if(node.left!null){queue.offer(node.left);}if(node.right!null){queue.offer(node.right);}}ans.add(level);}returnans;}}为什么要记录sizesize表示当前层有多少个节点。每次只处理当前层的size个节点就可以把每一层单独放进一个列表。这和上一篇 BFS 中的按层统计是一模一样的思想。层序遍历就是二叉树上的 BFS队列用于保证节点按层访问。复杂度分析树遍历的成本无论是前序、中序、后序还是层序遍历都会访问每个节点一次。所以时间复杂度都是O(n)其中n是树中节点数量。空间复杂度要分情况递归 DFS最坏O(n)平衡树约O(log n)迭代 DFS栈空间最坏O(n)BFS 层序遍历队列空间最坏O(n)如果不计算返回答案数组只计算额外辅助结构上面的结论成立。常见坑点二叉树遍历最容易错在哪里1. 忘记处理空树空树输入非常常见。递归写法中要有if(rootnull){return;}如果是返回列表的函数也要能返回空列表。2. 混淆前序、中序、后序记住一句话前中后说的是根节点的位置前序根在前中序根在中间后序根在后3. 迭代前序入栈顺序写反前序遍历要求根 - 左 - 右由于栈后进先出所以应该先压右再压左4. 中序迭代忘记一路向左中序迭代的关键是while(cur!null){stack.push(cur);curcur.left;}如果没有这个过程就无法保证先访问左子树。5. 层序遍历没有按层处理如果题目要求返回每一层一个列表就必须记录当前层节点数量intsizequeue.size();否则所有节点会混在一个列表里。模板总结二叉树遍历常用写法前序递归模板voidpreorder(TreeNoderoot){if(rootnull){return;}visit(root);preorder(root.left);preorder(root.right);}中序递归模板voidinorder(TreeNoderoot){if(rootnull){return;}inorder(root.left);visit(root);inorder(root.right);}后序递归模板voidpostorder(TreeNoderoot){if(rootnull){return;}postorder(root.left);postorder(root.right);visit(root);}层序遍历模板QueueTreeNodequeuenewLinkedList();queue.offer(root);while(!queue.isEmpty()){intsizequeue.size();for(inti0;isize;i){TreeNodenodequeue.poll();if(node.left!null){queue.offer(node.left);}if(node.right!null){queue.offer(node.right);}}}总结二叉树是算法题中非常高频的数据结构。它的很多题目都建立在遍历基础上。你可以重点记住下面几句话二叉树每个节点最多有两个孩子树天然适合递归因为子树本身也是树前序、中序、后序都属于 DFS前中后说的是根节点的位置前序是根、左、右中序是左、根、右后序是左、右、根层序遍历是 BFS需要用队列递归写法更简洁迭代写法本质是用栈模拟递归中序遍历在二叉搜索树中会得到有序序列掌握遍历之后后面的最大深度、路径和、二叉搜索树等题目都会更容易理解。