企业官网建设流程全解析

网站建设哪家较好,朋友圈网站广告怎么做,石家庄工信部网站备案,百度网盘app官网【LeetCode 110】平衡二叉树#xff1a;如何用一个“Magic Number”将复杂度降为 O(N)#xff1f; 判断一棵二叉树是否是平衡二叉树#xff08;Balanced Binary Tree#xff09;#xff0c;是数据结构面试中的一道“分水岭”题目。 很多同学能立刻写出第一种解法#xff…【LeetCode 110】平衡二叉树如何用一个“Magic Number”将复杂度降为 O(N)判断一棵二叉树是否是平衡二叉树Balanced Binary Tree是数据结构面试中的一道“分水岭”题目。很多同学能立刻写出第一种解法但往往会被面试官指出效率过低。如何从O(N2)O(N^2)O(N2)的暴力解法进化到O(N)O(N)O(N)的最优解法秘密就在于如何巧妙地利用递归的返回值。题目回顾给定一个二叉树判断它是否是高度平衡的二叉树。一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。解法一自顶向下直观但低效这是最符合人类直觉的思路既然要求“每个节点”都要平衡那我就写一个计算高度的方法然后挨个检查每一个节点。1. 代码实现classSolution{// 主函数publicbooleanisBalanced(TreeNoderoot){if(rootnull)returntrue;// 1. 先计算当前节点左右子树的高度intleftTreeHeightgetHeight(root.left);intrightTreeHeightgetHeight(root.right);// 2. 核心判断三条标准必须同时满足// A. 当前节点的高度差 1// B. 左子树也是平衡的 (递归)// C. 右子树也是平衡的 (递归)return(Math.abs(leftTreeHeight-rightTreeHeight)2)isBalanced(root.left)isBalanced(root.right);}// 辅助函数纯粹计算高度publicintgetHeight(TreeNoderoot){if(rootnull)return0;returnMath.max(getHeight(root.left),getHeight(root.right))1;}}2. 为什么它不够好这个解法采用了前序遍历的思想先办事再下放。它的致命伤在于重复计算在判断root是否平衡时getHeight已经遍历了所有的子节点。接着判断root.left是否平衡时又要重新调用getHeight遍历root.left底下的子节点。越底层的节点被重复访问的次数越多。时间复杂度O(N2)O(N^2)O(N2)。在树退化成链表时效率极低。解法二自底向上高效的最优解为了消除重复计算我们需要采用后序遍历的思想不要总是上级向下级问话而是让下级把结果汇报上来。如果某个子树发现自己不平衡了它不应该只是简单地返回高度而是应该返回一个错误信号Magic Number比如-1。父节点一旦收到-1就知道下面出事了直接停止计算继续向上报错。1. 代码实现classSolution{publicbooleanisBalanced(TreeNoderoot){// 如果 getHeight 返回 -1说明这棵树是不平衡的returngetHeight(root)0;}// 修改后的 getHeight既返回高度又兼职“报警”// 约定如果不平衡返回 -1如果平衡返回实际高度publicintgetHeight(TreeNoderoot){if(rootnull)return0;// 1. 先算左边intleftHeightgetHeight(root.left);// 【剪枝】如果左边已经出事了返回-1那我也直接报错不往下走了if(leftHeight0){return-1;}// 2. 再算右边intrightHeightgetHeight(root.right);// 【剪枝】如果右边出事了或者我自己左右差 1都报错if(rightHeight0||Math.abs(leftHeight-rightHeight)1){return-1;}else{// 3. 一切正常汇报真实高度returnMath.max(leftHeight,rightHeight)1;}}}2. 核心难点图解-1 是如何产生和传递的很多初学者卡在leftHeight 0这个判断上。到底谁产生了-1谁又接收了-1我们通过一个具体的不平衡树来模拟全过程1 -- 根节点 / \ 2 3 / 4 / 5(注节点 2 的左树高度为 2右树为 0差值为 2不平衡)代码执行流程模拟第一阶段深入底层程序递归直到最底部的节点 5。getHeight(5)左右为空返回高度1。第二阶段向上汇报回到节点 4。getHeight(4)左边收到 1右边是 0。高度差 1。正常返回高度2。第三阶段始作俑者错误产生的源头回到节点 2。它调用getHeight(4)变量leftHeight拿到值2。它调用getHeight(null)变量rightHeight拿到值0。关键判断Math.abs(2 - 0) 1成立动作节点 2 发现自己不平衡于是触发return -1;。注意这里是-1第一次被制造出来的地方。第四阶段传声筒错误的传递回到根节点 1。它执行第一行代码int leftHeight getHeight(root.left);即访问节点 2。接收因为节点 2 返回了-1所以变量leftHeight现在等于-1。剪枝if(leftHeight0){return-1;}条件成立根节点 1 甚至不需要去计算右子树节点 3的高度直接向外抛出-1。3. 公司职级比喻如果把这棵树比作公司节点 2底层经理发现部门出了大问题不平衡于是向上级汇报代码-1而不是业绩。节点 1总经理收到下属汇报的-1立刻明白出事了于是停止计算公司总业绩直接向董事会也汇报-1。isBalanced董事会看到最终结果是-1判定结果为false。总结与对比维度解法一自顶向下解法二自底向上遍历思想前序 (Preorder)后序 (Postorder)核心操作计算高度与判断逻辑分离计算高度的同时判断平衡时间复杂度O(N2)O(N^2)O(N2)(最差情况)O(N)O(N)O(N)(最优)效率低 (大量重复计算子节点高度)高 (每个节点只访问一次)返回值含义仅代表是否平衡 (Boolean)既代表高度又用 -1 代表不平衡最终结论解法二通过引入-1作为状态标记巧妙地将“计算高度”和“检测平衡”融合在了一次遍历中实现了时间复杂度的降维打击。掌握这种“利用返回值携带额外信息”的技巧是解决二叉树问题的核心能力之一。