一天一道Hot100（39）：二叉树的遍历

LeetCode 94. 二叉树的中序遍历个人主页 我不会起名字322 欢迎各位大佬莅临其他栏目 技术栈学习笔记 其他栏目 力扣Hot100题目解析 其他栏目 Go项目学习笔记 前言前面的回溯系列里我们一直在强调三要素——路径、选择列表、结束条件。但算法题不是只有回溯一种套路。从今天开始我们换一条线专门聊二叉树。二叉树题有个特点代码极短但递归逻辑极其密集。一道题可能只有五六行但每一行都在做递归调用如果对递归到底在干什么没有直觉看代码就像看天书。所以这个系列的第一篇我们不急着刷难题先把遍历这个最基础、也最核心的骨架吃透。中序遍历是理解二叉树递归的入口——把它想清楚了前序、后序只是换个位置的事后面的层序遍历、路径求和、最近公共祖先也都是在这个骨架上长出来的。首先我们说二叉树的递归到底是干了什么事递归是一种分而治之的策略当你把一棵树拆成根 左子树 右子树并且发现左子树和右子树又是同样结构的树时递归就自然出现了。遍历题用递归访问每个节点并在访问时收集答案。这道题稍微特殊一点——我们不是在每个节点处都做同一件事而是在左子树和右子树之间插入访问根的动作这个插入位置的不同直接决定了是前序、中序还是后序。递归的终止条件这是二叉树递归要看的第一个数据。这道题的终止条件就是当前节点为空。空节点不是没有节点而是递归的地基——没有它递归就会无限往下走。所以每个递归函数的第一行几乎都是if node nil { return }。当前节点要做什么这是二叉树递归要看的第二个数据。中序遍历里当前节点要做的事就是把它的值追加到结果集。但注意这个动作不是随便做的——它必须发生在左子树递归回来之后、右子树递归开始之前。这个位置就是中序的序。递归的去向这是二叉树递归要看的第三个数据。当前节点处理完之后要往哪里递归答案是左子树和右子树。但先去哪、后去哪以及访问根夹在中间哪个位置就是三种遍历的区别所在。整体的一个模板还是这样的functraverse(node*TreeNode){ifnodenil{return}// 位置 A前序在这里访问根traverse(node.Left)// 递归左子树// 位置 B中序在这里访问根traverse(node.Right)// 递归右子树// 位置 C后序在这里访问根}记住这三个位置 A、B、C——它们就是前序、中序、后序的全部秘密。下面我们来看一道题目深入理解一下给定一个二叉树的根节点root返回它的中序遍历。示例 1输入root [1,null,2,3] 输出[1,3,2]示例 2输入root [] 输出[]示例 3输入root [1] 输出[1]提示树中节点数目在范围[0, 100]内-100 Node.val 100遍历的规则在动手写代码之前先想清楚一次合法的遍历到底要满足什么。二叉树的递归定义决定了三件事空节点是递归的终点遇到nil直接返回这是所有遍历方式共用的终止条件访问顺序决定遍历名称根在左之前叫前序根在左右之间叫中序根在右之后叫后序左右子树的递归结构相同每个节点都把自己当成一棵新的子树来处理第 2 条尤其关键。比如示例 1 的[1,null,2,3]中序遍历之所以输出[1,3,2]是因为先递归到1的左子树空然后访问1再递归到1的右子树节点2在2这里先递归到它的左子树节点3访问3再访问2最后递归2的右子树空。整个顺序就是左 → 根 → 右。首先我们不需要排序也不需要一维数组。这道题的输入是一棵二叉树没有候选数组所以组合总和里的sort.Ints和startIndex在这里都用不上。这正说明二叉树题有自己的一套骨架不必硬套回溯。其次我们要定义几个数据一个是结果集用来收集遍历到的节点值res:[]int{}注意这里不像单词搜索那样传一个index因为树的结构本身就在递归栈里我们只需要一个地方把节点值存下来即可。一个是递归函数本身它的参数是当前节点functraverse(node*TreeNode)注意这里不像括号生成那样传open, close两个计数器因为树题要处理的是节点而不是数量。上面两个是确定的最后一个看题目不同来自己确定。这道题我们需要一个闭包来捕获结果集vartraversefunc(node*TreeNode)traversefunc(node*TreeNode){ifnodenil{return}// 中序左 → 根 → 右traverse(node.Left)resappend(res,node.Val)traverse(node.Right)}有了上面的数据我们现在来套用模板来写这道题目functraverse(node*TreeNode){首先是这个大框架终止条件肯定要判 nodenil这道题的当前节点要做什么不是数组而是由 node 动态决定的-访问根节点的值插入到左子树和右子树之间}if满足终止条件{这里的终止条件就是 nodenil直接返回不做任何访问}//这里我们要想如果还能往下走怎么办呢显然继续下面的递归即可//那如果左右子树都为空呢那就自然返回让上一层去处理// 遍历三个动作顺序由遍历方式决定traverse(node.Left)// 动作一递归左子树resappend(res,node.Val)// 动作二访问根中序traverse(node.Right)// 动作三递归右子树注意一个细节这道题和回溯题不一样——递归的入口不是某个固定起点而是整棵树的根节点。所以最外层只需要调用一次varres[]inttraverse(root)returnres只要中途node变成了nil就直接返回不用继续往下走了——这就是遍历整棵树和搜索特定路径的区别。因此我们最后改造的函数就是/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funcinorderTraversal(root*TreeNode)[]int{res:[]int{}vartraversefunc(node*TreeNode)traversefunc(node*TreeNode){// 终止条件当前节点为空ifnodenil{return}// 中序左 → 根 → 右traverse(node.Left)// 递归左子树resappend(res,node.Val)// 访问根节点traverse(node.Right)// 递归右子树}traverse(root)returnres}进阶能不能不用闭包用显式的栈可以。递归的本质是编译器帮我们维护了一个调用栈我们完全可以自己用stack来模拟这个过程。中序遍历的迭代版本稍微有点绕因为访问根这个动作要延迟到左子树处理完之后。funcinorderTraversal(root*TreeNode)[]int{res:[]int{}stack:[]*TreeNode{}cur:rootforcur!nil||len(stack)0{// 一路向左把沿途节点压栈forcur!nil{stackappend(stack,cur)curcur.Left}// 弹出栈顶访问它curstack[len(stack)-1]stackstack[:len(stack)-1]resappend(res,cur.Val)// 转向右子树curcur.Right}returnres}这份代码比递归版本更长但把递归栈这个隐式结构显式化了——这就是递归和迭代的对应关系。尤其注意stack append(stack, cur)和stack stack[:len(stack)-1]这一对操作它们分别对应递归里的进入子树和从子树返回。拓展前序、中序、后序遍历的逻辑三种遍历共用同一套递归骨架唯一的区别是**访问根节点这一动作放在位置 A、B 还是 C**。用一张表就能看清遍历方式访问顺序访问根的位置示例 1 输出前序根 → 左 → 右位置 A递归左子树之前[1,2,3]中序左 → 根 → 右位置 B左右子树之间[1,3,2]后序左 → 右 → 根位置 C递归右子树之后[3,2,1]对应的代码只需要调换三行// 前序根 → 左 → 右funcpreorderTraversal(root*TreeNode)[]int{res:[]int{}vartraversefunc(node*TreeNode)traversefunc(node*TreeNode){ifnodenil{return}resappend(res,node.Val)// 位置 A访问根traverse(node.Left)// 递归左子树traverse(node.Right)// 递归右子树}traverse(root)returnres}// 中序左 → 根 → 右funcinorderTraversal(root*TreeNode)[]int{res:[]int{}vartraversefunc(node*TreeNode)traversefunc(node*TreeNode){ifnodenil{return}traverse(node.Left)// 递归左子树resappend(res,node.Val)// 位置 B访问根traverse(node.Right)// 递归右子树}traverse(root)returnres}// 后序左 → 右 → 根funcpostorderTraversal(root*TreeNode)[]int{res:[]int{}vartraversefunc(node*TreeNode)traversefunc(node*TreeNode){ifnodenil{return}traverse(node.Left)// 递归左子树traverse(node.Right)// 递归右子树resappend(res,node.Val)// 位置 C访问根}traverse(root)returnres}为什么顺序一换结果就完全不同因为二叉树的递归定义是根 左子树 右子树而遍历的本质就是决定在递归的哪一步处理根。前序在进入子树之前处理根中序在左子树回来之后处理根后序在右子树回来之后处理根。迭代版本的区别同样体现在访问根的时机上前序迭代用栈先压右再压左弹出即访问中序迭代用栈一路向左压栈弹出时访问再转向右后序迭代用栈按根 → 右 → 左压栈最后反转结果复杂度分析时间复杂度O(n)其中n是节点数。每个节点恰好被访问一次。空间复杂度O(h)其中h是树的高度。递归栈深度等于树高最坏情况下链式树为 O(n)平均情况下平衡树为 O(log n)。总结回过头看这道题的核心就是三个位置 A、B、C遍历方式访问根的位置代码体现前序位置 Ares append(res, node.Val)放在两次traverse之前中序位置 Bres append(res, node.Val)放在两次traverse之间后序位置 Cres append(res, node.Val)放在两次traverse之后和前面的回溯题对比一下区别一目了然组合总和括号生成单词搜索二叉树遍历核心结构一维数组两个计数器二维网格递归树终止条件curSum targetlen(path) 2*nindex len(word)node nil访问时机收集所有解收集所有解找到一条就收手位置 A/B/C 决定遍历方式关键操作做选择 / 撤销选择做选择 / 撤销选择做选择 / 撤销选择递归左 / 访问根 / 递归右遍历是二叉树的地基。把中序的递归逻辑想清楚前序和后序只是把append换一行的事把递归栈和显式栈的对应关系想清楚迭代版本也就不再神秘。后面的层序遍历、路径求和、最近公共祖先都会在这个骨架上继续长。本文是 《算法题目解析系列》 的第 [39] 篇本系列将持续更新每篇都提供清晰的思路与编程语言实现。欢迎关注第一时间获取更新。如果你有想看的题目也可以在评论区留言告诉我。