企业官网建设流程全解析

网站空间 数据库,英文医疗网站建设,做网站要会哪些软件,网站建设协题目描述给定一个二叉树#xff0c;判断它是否是 平衡二叉树 示例 1#xff1a;输入#xff1a;root [3,9,20,null,null,15,7] 输出#xff1a;true示例 2#xff1a;输入#xff1a;root [1,2,2,3,3,null,null,4,4] 输出#xff1a;false示例 3#xff1a;输入判断它是否是 平衡二叉树示例 1输入root [3,9,20,null,null,15,7]输出true示例 2输入root [1,2,2,3,3,null,null,4,4]输出false示例 3输入root []输出true提示树中的节点数在范围[0, 5000]内-104 Node.val 104解决方案这段代码的核心功能是判断一棵二叉树是否为平衡二叉树即每个节点的左右子树高度差的绝对值不超过 1采用「后序遍历 递归剪枝」的思路实现在计算子树高度的同时校验平衡条件时间复杂度O(n)n为节点数空间复杂度O(h)h为树的高度是该问题的最优解法。核心逻辑代码将 “计算子树高度” 和 “校验平衡条件” 融合在同一个递归函数中通过返回特殊值-1实现剪枝避免重复遍历递归辅助函数node_height既计算节点的高度又实时校验平衡条件边界条件空节点高度为0递归计算左子树高度left_h若左子树已不平衡left_h-1直接返回-1剪枝无需计算右子树同理递归计算右子树高度right_h若右子树不平衡直接返回-1校验当前节点平衡条件若左右子树高度差的绝对值 1返回-1标记当前子树不平衡若平衡返回当前节点的高度max(left_h, right_h)1主函数isBalanced空树直接返回true空树是平衡的调用node_height(root)若返回值不为-1说明整棵树平衡返回true否则返回false。总结核心思路后序遍历先算左右子树高度再判断当前节点在计算高度的同时校验平衡用-1剪枝避免无效递归关键优化相比 “先算所有节点高度再逐个校验” 的暴力解法该思路只需一次遍历时间效率更高效率特点每个节点仅被访问一次时间O(n)递归栈空间取决于树的高度平衡树为O(log n)退化为链表时为O(n)。函数源码/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int node_height(TreeNode* node){ if(!node) return 0; int left_hnode_height(node-left); if(left_h-1){ return -1; } int right_hnode_height(node-right); if(right_h-1){ return -1; } if(abs(right_h-left_h)1){ return -1; } return max(left_h,right_h)1; } bool isBalanced(TreeNode* root) { if(!root) return true; return node_height(root)!-1; } };