二叉树的构造、合并与二叉搜索树

文章目录二叉树的构造、合并与二叉搜索树1. 引入为什么要学习这些2. 二叉树的构造2.1 从中序与后序遍历构造二叉树2.2 从前序与中序遍历构造二叉树3. 二叉树的合并4. 二叉搜索树BST——从无序到有序4.1 从一个生活场景引入4.2 BST的核心思想大小关系决定位置4.3 BST的核心操作不讲代码主讲思路查找像查字典一样插入找到空位就坐删除最难的操作4.4 BST的灵魂中序遍历4.5 什么时候用BST5. 从有序数组构造平衡BST6. 总结对比表7. 易错点总结二叉树的构造、合并与二叉搜索树1. 引入为什么要学习这些在解决实际问题时我们常常需要面对这样的场景发现了某棵二叉树的中序和后序遍历记录如何还原这棵树的原貌图像处理中需要将两张重叠的图片融合对应到二叉树就是节点的合并数据库索引为什么能快速查找数据秘密就在于二叉搜索树的结构这些问题看似不同但核心都是二叉树的结构操作。掌握它们你就能真正理解二叉树的灵魂。2. 二叉树的构造2.1 从中序与后序遍历构造二叉树106. 从中序与后序遍历序列构造二叉树 - 力扣LeetCode核心原理要理解这个构造过程先看两种遍历的特点遍历方式顺序特点中序遍历左 → 根 → 右根节点把左右子树分开后序遍历左 → 右 → 根最后一个节点一定是根节点图解过程以这棵树为例3 / \ 9 20 / \ 15 7中序[9, 3, 15, 20, 7]后序[9, 15, 7, 20, 3]构造步骤后序最后一个3是根节点在中序中找到3左边[9]是左子树右边[15,20,7]是右子树左子树中序[9]后序[9]→ 节点9右子树中序[15,20,7]后序[15,7,20]→ 递归构建代码实现structTreeNode*build(int*inorder,int*postorder,intinStart,intinEnd,intpostStart,intpostEnd){if(inStartinEnd||postStartpostEnd){// 递归终止条件区间无效returnNULL;}introotValuepostorder[postEnd];// 后序最后一个节点是当前子树的根structTreeNode*root(structTreeNode*)malloc(sizeof(structTreeNode));root-valrootValue;intposition;// 在中序中找到根的位置for(positioninStart;positioninEnd;position){if(inorder[position]rootValue){break;}}intleftSizeposition-inStart;// 关键计算左子树的节点数root-leftbuild(inorder,postorder,inStart,position-1,postStart,postStartleftSize-1);// 递归构建左右子树root-rightbuild(inorder,postorder,position1,inEnd,postStartleftSize,postEnd-1);returnroot;}structTreeNode*buildTree(int*inorder,intinorderSize,int*postorder,intpostorderSize){if(inorderSize0||postorderSize0){returnNULL;}returnbuild(inorder,postorder,0,inorderSize-1,0,postorderSize-1);}关键点解析leftSize position - inStart左子树节点数后序区间划分左子树[postStart, postStartleftSize-1]右子树[postStartleftSize, postEnd-1]中序区间划分左子树[inStart, position-1]右子树[position1, inEnd]额这个范围感觉难记的话我都是写的时候边画图边数的2.2 从前序与中序遍历构造二叉树105. 从前序与中序遍历序列构造二叉树 - 力扣LeetCode核心原理前序[根, 左子树, 右子树]→ 第一个是根中序[左子树, 根, 右子树]思路与前后构造类似只是根的位置在前序第一个// 原理类似3. 二叉树的合并617. 合并二叉树 - 力扣LeetCode问题给定两棵二叉树将它们合并成一棵新树。合并规则如下如果两个节点重叠新节点值为两节点值之和否则不为NULL的节点直接作为新树的节点图解Tree1 Tree2 合并后 1 2 3 / \ / \ / \ 3 2 1 3 4 5 / \ / \ 5 4 5 4递归思路如果root1为空返回root2如果root2为空返回root1都不为空创建新节点值为两节点和递归合并左子树和右子树代码实现structTreeNode*mergeTrees(structTreeNode*root1,structTreeNode*root2){if(root1NULL){// 处理一方为空的情况returnroot2;}if(root2NULL){returnroot1;}structTreeNode*new(structTreeNode*)malloc(sizeof(structTreeNode));// 都不为空创建新节点new-valroot1-valroot2-val;new-leftmergeTrees(root1-left,root2-left);// 递归合并左右子树new-rightmergeTrees(root1-right,root2-right);returnnew;}复杂度分析时间复杂度O(min(n, m))n和m为两棵树节点数空间复杂度O(min(h1, h2))递归栈深度4. 二叉搜索树BST——从无序到有序4.1 从一个生活场景引入想象你在整理书架如果书是按随机顺序摆放的找一本书需要一本本翻过去O(n)如果书是按拼音顺序摆放的你可以用二分法快速定位BST就是二叉树的按拼音顺序摆放——它让查找从O(n)变成了O(h)。4.2 BST的核心思想大小关系决定位置定义三句话比代码更重要对于任意节点左子树所有节点都比它小右子树所有节点都比它大左右子树也满足这两条图解对比普通二叉树 二叉搜索树 5 5 / \ / \ 3 8 3 8 / \ / \ / \ \ 1 4 7 9 1 4 9 \ \ 6 7?在BST中7不能放在9的右边因为79应该去9的左子树。这就是规则的力量。4.3 BST的核心操作不讲代码主讲思路查找像查字典一样思路比当前节点小去左子树比当前节点大去右子树相等找到了为什么快每走一步搜索范围就减半——这就是树的二分查找。插入找到空位就坐思路和查找一模一样只是最后一步——找到空位了就坐在这里关键理解插入的新节点永远在叶子位置不会破坏树的结构删除最难的操作删除为什么复杂因为要维持BST的性质。三种情况用生活比喻情况生活比喻处理方法删叶子公司里最底层的员工离职直接让他走没人受影响删单支节点一个主管离职他手下有个员工让这个员工直接顶替主管位置删双支节点一个经理离职手下有两个主管找个合适的人来接替通常是右子树里最小的那个主管图解双支节点删除删除38 / \ 3 10 / \ \ 2 6 14 / / \ / 1 4 7 13 \ 5步骤找到3节点判断3节点的左右子树情况都为空左空右空都存在按照判断进行删除操作如果判断为左右都存在那么先找到3节点右子树中的最小节点即4并将其替换3。即8 / \ 4 10 / \ \ 2 6 14 / / \ / 1 ? 7 13 \ 5最后继续递归将“”的位置删除即可。4.4 BST的灵魂中序遍历这是BST最神奇的性质对BST进行中序遍历得到的是递增序列5 / \ 3 8 / \ \ 1 4 9 中序遍历1,3,4,5,8,9 递增这意味着要判断一棵树是不是BST中序遍历看是否递增要把BST转成有序数组中序遍历要找BST的第k小元素中序遍历到第k个4.5 什么时候用BST适合数据是动态插入删除的数据需要有序性范围查询、第k小元素插入顺序比较随机不适合数据是静态的数组二分查找更快插入顺序有序会退化成链表只需要查找5. 从有序数组构造平衡BST108. 将有序数组转换为二叉搜索树 - 力扣LeetCode问题给定有序数组构造一棵高度平衡的二叉搜索树思路每次取中间元素作为根递归构建左右子树图解数组[-10, -3, 0, 5, 9] 0 / \ -3 9 / / -10 5代码实现structTreeNode*buildBST(int*nums,intleft,intright){if(leftright)returnNULL;intmidleft(right-left)/2;// 取中间元素作为根structTreeNode*root(structTreeNode*)malloc(sizeof(structTreeNode));root-valnums[mid];root-leftbuildBST(nums,left,mid-1);// 递归构建左右子树root-rightbuildBST(nums,mid1,right);returnroot;}structTreeNode*sortedArrayToBST(int*nums,intnumsSize){if(numsSize0)returnNULL;returnbuildBST(nums,0,numsSize-1);}6. 总结对比表操作核心思想关键点时间复杂度中后构造后序定根中序分左右计算左子树大小O(n²)找根位置合并二叉树同步递归遍历处理空节点O(min(n,m))BST验证中序遍历递增严格递增判断O(n)BST查找利用大小关系每次减少一半O(h)BST插入找到空位插入保持BST性质O(h)BST删除分三种情况处理双子节点找后继O(h)有序数组→BST二分递归取中间元素O(n)注h为树高最坏O(n)最好O(log n)7. 易错点总结构造时下标计算中序找根时左子树长度 根索引 - 中序起始后序区间划分右子树后序结束位置是postEnd - 1因为最后一个是根合并时的空指针处理先判断一方为空的情况避免空指针访问BST验证的严格性必须是严格递增就不行BST删除双子节点替换后要递归删除那个被替换的节点递归终止条件什么时候返回NULL什么时候返回节点