个人主页 我不会起名字322 欢迎各位大佬莅临其他栏目 技术栈学习笔记 其他栏目 力扣Hot100题目解析 其他栏目 Go项目学习笔记 其他栏目 redis 二叉树的遍历与二叉搜索树把递归、迭代、还原树一次讲透文章目录二叉树的遍历与二叉搜索树把递归、迭代、还原树一次讲透一、先把结构定死二、三种遍历差的只是哪一次经过时输出三、把递归改成迭代用显式栈自己维护经过四、已知两种遍历怎么把树还原回来五、二叉搜索树让查找有了方向六、复杂度与退化为什么裸 BST 不够用七、收个尾刚开始学二叉树的时候我卡住的不是语法而是脑子里没有一个统一的模型。前序、中序、后序三个名字背得滚瓜烂熟可一旦题目换成已知前序和中序还原这棵树手就停了等到二叉搜索树的删除节点三种情况更是每次都现推。后来我发现问题出在我把遍历当成了三个独立的知识点去记而它其实只是同一件事的三个观察窗口。这篇文章就用一棵树走到底遍历、还原、BST 的查找插入删除全部围绕下面这棵树展开。把它吃透比刷十道不相干的题有用。一、先把结构定死typeTreeNodestruct{ValintLeft,Right*TreeNode}就这三行。树是非线性结构但节点本身只记三样东西自己的值、左孩子、右孩子。空树用nil表示。这里有个新手常犯的混淆完全二叉树可以用数组存堆就是这么干的但普通二叉树不行。堆用数组是因为它必须完全下标i的左右孩子固定在2i1和2i2没有任何浪费。而二叉搜索树的形状由插入顺序决定中间可能空出一大片硬塞进数组就是拿空间换一个并不存在的规律。所以我们一律用指针链起来。文章里统一用这棵树它恰好还是一棵合法的二叉搜索树8 / \ 3 10 / \ \ 1 6 14 / \ / 4 7 13二、三种遍历差的只是哪一次经过时输出先看递归写法三份代码骨架完全一样funcpreorder(n*TreeNode,out*[]int){ifnnil{return}*outappend(*out,n.Val)// 第 1 次经过根preorder(n.Left,out)preorder(n.Right,out)}funcinorder(n*TreeNode,out*[]int){ifnnil{return}inorder(n.Left,out)*outappend(*out,n.Val)// 第 2 次经过inorder(n.Right,out)}funcpostorder(n*TreeNode,out*[]int){ifnnil{return}postorder(n.Left,out)postorder(n.Right,out)*outappend(*out,n.Val)// 第 3 次经过}如果只把它们当成要背的三个顺序那确实容易乱。换成递归序的视角就清楚了递归过程中每一个节点都会被经过三次——刚进来一次、左子树回来一次、右子树回来一次。第 1 次经过时打印 → 前序根左右第 2 次经过时打印 → 中序左根右第 3 次经过时打印 → 后序左右根打印语句所在的位置就是第几次经过。三份代码只有那一行的位置不同这不是巧合是本质。套进上面那棵树遍历方式序列前序8, 3, 1, 6, 4, 7, 10, 14, 13中序1, 3, 4, 6, 7, 8, 10, 13, 14后序1, 4, 7, 6, 3, 13, 14, 10, 8注意中序那一行1 3 4 6 7 8 10 13 14正好是升序。这不是这棵树的运气而是二叉搜索树的定义决定的后面第六节会用到。三、把递归改成迭代用显式栈自己维护经过递归跑得爽但有两类场景必须换迭代深度太大。斜树有 10 万个节点递归深度就是 10 万C/C/Java 的线程栈撑不住会栈溢出。Go 的 goroutine 栈能自动扩容不容易炸但深度太大照样是隐患。面试官就说不许用递归。写迭代的关键是想清楚递归帮你干了什么它把待处理的节点存在了调用栈里。那迭代就自己开一个栈把这个活儿接管过来。前序出栈即访问然后把右孩子、左孩子依次压栈。funcpreorderIter(root*TreeNode)[]int{ifrootnil{returnnil}varres[]intstack:[]*TreeNode{root}forlen(stack)0{n:stack[len(stack)-1]stackstack[:len(stack)-1]resappend(res,n.Val)ifn.Right!nil{stackappend(stack,n.Right)// 先压右}ifn.Left!nil{stackappend(stack,n.Left)// 后压左所以左先出栈}}returnres}压栈顺序反过来写是因为栈是后进先出。想先访问左子树就得让左孩子后压。中序一路向左压栈压不动了就弹一个出来访问然后转向它的右子树。funcinorderIter(root*TreeNode)[]int{varres[]intstack:[]*TreeNode{}cur:rootforcur!nil||len(stack)0{forcur!nil{// 一路向左stackappend(stack,cur)curcur.Left}curstack[len(stack)-1]// 左边到头的那个节点该第 2 次经过了stackstack[:len(stack)-1]resappend(res,cur.Val)curcur.Right// 左子树处理完转向右子树}returnres}这段是三种迭代里最容易写错的建议记一个判断标准内层for只管左外层循环负责弹栈 转右两者不要混。后序有个很省事的技巧——先按根 → 右 → 左的顺序遍历最后把结果整个反转就得到左 → 右 → 根。funcpostorderIter(root*TreeNode)[]int{ifrootnil{returnnil}varres[]intstack:[]*TreeNode{root}forlen(stack)0{n:stack[len(stack)-1]stackstack[:len(stack)-1]resappend(res,n.Val)// 此刻拿到的是 根 → 右 → 左ifn.Left!nil{stackappend(stack,n.Left)}ifn.Right!nil{stackappend(stack,n.Right)}}fori,j:0,len(res)-1;ij;i,ji1,j-1{res[i],res[j]res[j],res[i]}returnres}比起用一个指针记录上次访问的节点那种严格模拟递归的写法这个反转法好写也好懂代价只是多一次 O(n) 的反转复杂度没变。层序遍历广度优先是另一套路子用队列而不是栈funclevelOrder(root*TreeNode)[][]int{ifrootnil{returnnil}varout[][]intqueue:[]*TreeNode{root}forlen(queue)0{size:len(queue)// 关键先锁定这一层的节点个数level:make([]int,0,size)fori:0;isize;i{n:queue[0]queuequeue[1:]levelappend(level,n.Val)ifn.Left!nil{queueappend(queue,n.Left)}ifn.Right!nil{queueappend(queue,n.Right)}}outappend(out,level)}returnout}size那一行是分层的关键。不锁住它你就分不清队列里哪些是当前层、哪些是下一层按层分组立刻失效。小提醒queue queue[1:]这种写法在切片底层数组上会一直往前挪元素本身不会被回收。数据量大的时候改成head下标更稳妥head:0forheadlen(queue){n:queue[head]head// ...}四、已知两种遍历怎么把树还原回来这是遍历最实用的一次反向使用也是面试高频。规律只有一条某种遍历里最先/最后出现的那个节点就是根。前序第一个是根后序最后一个是根中序根在中间左边全是左子树右边全是右子树前序 中序的流程前序第一个是根在这棵树里是8去中序里找8左边1 3 4 6 7是左子树右边10 13 14是右子树左子树有 5 个节点那么前序里根后面的 5 个就是左子树的前序左右分别递归。用代码实现时别每层都去扫一遍中序找根的位置——那会退化。先用 map 把值 → 中序下标缓存起来整棵树就回到 O(n)funcbuildTree(preorder,inorder[]int)*TreeNode{idx:make(map[int]int,len(inorder))fori,v:rangeinorder{idx[v]i}varbuildfunc(preLo,preHi,inLo,inHiint)*TreeNode buildfunc(preLo,preHi,inLo,inHiint)*TreeNode{ifpreLopreHi{returnnil}rootVal:preorder[preLo]// 前序第一个就是根pos:idx[rootVal]// 它在中序里的位置leftSize:pos-inLo// 左子树有多少个节点returnTreeNode{Val:rootVal,Left:build(preLo1,preLoleftSize,inLo,pos-1),Right:build(preLoleftSize1,preHi,pos1,inHi),}}returnbuild(0,len(preorder)-1,0,len(inorder)-1)}中序 后序同理只是根要从后序的末尾取rootVal:postorder[postHi]// 左子树后序 [postLo, postLoleftSize-1]// 右子树后序 [postLoleftSize, postHi-1]那前序 后序为什么不行这两个序列都能定位根但都没法告诉你根后面的节点里哪些属于左子树。看个反例树 A1 只有左孩子 2 树 B1 只有右孩子 2 A 的前序: 1, 2 B 的前序: 1, 2 A 的后序: 2, 1 B 的后序: 2, 1两棵完全不同的树前序和后序一模一样。所以没有中序就没有分界线。记法很简单中序是唯一能切分左右子树的序列所以它必须出现。已知中序 任意另一种才能唯一确定一棵树。五、二叉搜索树让查找有了方向二叉搜索树BST在普通二叉树上加了一条约束任意节点的左子树中所有节点都小于它右子树中所有节点都大于它。请特别注意所有两个字。它约束的不是直接孩子而是整棵子树。这一点决定了验证 BST 时最容易踩的坑见本节最后。有了这条约束查找就有了方向感——每比较一次就能扔掉一半funcsearch(root*TreeNode,vint)*TreeNode{cur:rootforcur!nil{switch{casevcur.Val:curcur.Leftcasevcur.Val:curcur.Rightdefault:returncur}}returnnil}这就是二分查找在树上的形态时间复杂度是树高 O(h)。树平衡时 h log n。插入的思路是先按查找的路线走到底挂上去。要注意 BST 通常不允许重复值且需要用一个parent记录上一站否则走到nil时就丢了父节点funcinsert(root*TreeNode,vint)*TreeNode{ifrootnil{returnTreeNode{Val:v}}cur,parent:root,rootforcur!nil{ifvcur.Val{returnroot// 已存在不插入}parentcurifvcur.Val{curcur.Left}else{curcur.Right}}ifvparent.Val{parent.LeftTreeNode{Val:v}}else{parent.RightTreeNode{Val:v}}returnroot}删除是三种操作里唯一需要分情况的叶子节点直接删只有一个孩子让孩子顶替自己的位置有两个孩子找中序后继右子树里最小的节点也就是右子树一路向左到底来接替自己的值然后回到情况 1 或 2 把它删掉。funcdeleteNode(n*TreeNode,vint)*TreeNode{ifnnil{returnnil}switch{casevn.Val:n.LeftdeleteNode(n.Left,v)casevn.Val:n.RightdeleteNode(n.Right,v)default:ifn.Leftnil{// 情况 1、2右孩子顶上nil 也行returnn.Right}ifn.Rightnil{// 情况 1、2左孩子顶上returnn.Left}succ:n.Right// 情况 3找中序后继forsucc.Left!nil{succsucc.Left}n.Valsucc.Val// 值替换n.RightdeleteNode(n.Right,succ.Val)// 再去右子树里删掉那个后继}returnn}为什么找右子树最小因为它刚好是大于待删节点的所有值里最小的那个把它放上来左边依然全小、右边依然全大BST 的性质保住了。左子树最大节点前驱同样可以二选一。验证 BST 的坑很多人上来就写检查每个节点是否大于左孩子、小于右孩子这个判断是错的。看 LeetCode 上的经典反例[5,1,6,null,null,3,7]根 5右孩子 6而 6 的左孩子是 3。局部看3 6完全合法可 3 待的是根 5 的右子树它必须大于 5所以整棵树非法。正确做法有两条路// 写法一递归时把「上下界」往下传funcisValidBST(n*TreeNode,lo,hi*int)bool{ifnnil{returntrue}iflo!niln.Val*lo{returnfalse}ifhi!niln.Val*hi{returnfalse}returnisValidBST(n.Left,lo,n.Val)isValidBST(n.Right,n.Val,hi)}// 写法二利用「中序遍历必然严格递增」只记住前一个值funcisValidBST2(root*TreeNode)bool{varprev*intvarwalkfunc(*TreeNode)boolwalkfunc(n*TreeNode)bool{ifnnil{returntrue}if!walk(n.Left){returnfalse}ifprev!niln.Val*prev{returnfalse}v:n.Val prevvif!walk(n.Right){returnfalse}returntrue}returnwalk(root)}写法二更值得记住“BST 的中序遍历是升序”这句话本身就是一把万能钥匙——验证合法性只是它的一个用法求第 k 小的元素也是中序走到第 k 个就返回求最小/最大值则是一路向左/向右到底。六、复杂度与退化为什么裸 BST 不够用BST 的查找、插入、删除都沿着一条根到叶的路径走所以复杂度是O(h)结构查找插入删除说明普通数组O(n)O(n)O(n)无序只能扫有序数组O(log n)O(n)O(n)查找快但插入要搬元素二叉搜索树平衡O(log n)O(log n)O(log n)理想情况二叉搜索树退化O(n)O(n)O(n)退化成链表平衡树AVL / 红黑树O(log n)O(log n)O(log n)靠旋转维持平衡问题出在最后两行之间BST 的形状完全由插入顺序决定。按10, 20, 30, 40顺序插入得到的不是树而是一条往右甩的链表——这时 h n所有操作退化成 O(n)和扫数组没区别。所以生产环境里几乎没人直接用裸 BST。Java 的TreeMap、C 的std::map用的都是红黑树通过插入和删除后的旋转把树高摁在 O(log n)。顺带说一个 Go 的实际情况Go 标准库没有内置的有序 map。需要有序查找时常见做法是读多写少sort.Search在有序切片上二分缓存友好实际很快读写都频繁引入第三方 B 树实现如google/btree或者自己维护平衡树。选之前先想清楚读写比例不要为了看起来高级直接上红黑树。七、收个尾回头看这篇文章其实只讲了一个模型和它的两个用途递归序每个节点被经过三次打印发生在第几次就叫第几种遍历——这是如何访问BST 的约束左子树全小、右子树全大让查找每步扔一半——这是如何组织而它反过来又让中序遍历变成升序。遍历和 BST 不是两块知识它们咬合在同一个递归结构上。下次再遇到还原树或删除节点先问自己两句话“根在哪”、“左子树和右子树的分界线在哪”——大部分题目的入口就出来了。