网站多久备案一次吗,北京医疗网站建设公司,wordpress修改语言包目录,买国外域名 网站判断是否是平衡二叉树 题目描述数据范围题解解题思路递归算法代码实现代码解析时间和空间复杂度分析示例示例 1示例 2 总结 ) 题目描述
输入一棵节点数为 n 的二叉树#xff0c;判断该二叉树是否是平衡二叉树。平衡二叉树定义为#xff1a;
它是一棵空树。或者它的左右子树… 判断是否是平衡二叉树 题目描述数据范围题解解题思路递归算法代码实现代码解析时间和空间复杂度分析示例示例 1示例 2 总结 ) 题目描述
输入一棵节点数为 n 的二叉树判断该二叉树是否是平衡二叉树。平衡二叉树定义为
它是一棵空树。或者它的左右子树的高度差的绝对值不超过1并且左右子树本身也是平衡二叉树。
平衡二叉树的性质
空树被认为是平衡二叉树。每个节点的左右子树高度差不超过1。
数据范围
n ≤ 100每个节点的值 val 满足 0 ≤ val ≤ 1000
题解
解题思路
我们可以通过深度优先搜索DFS来判断一棵二叉树是否是平衡二叉树。具体步骤如下
定义树的高度 计算任意一个节点的左子树和右子树的高度。平衡性判断 如果某个节点的左右子树的高度差超过1树就不平衡否则继续判断该节点的左右子树。递归遍历 对树的每个节点递归地进行平衡性判断。
递归算法
我们可以通过递归来判断二叉树的平衡性同时在递归过程中计算树的高度。递归的核心思想是
如果左右子树的高度差超过1返回 false。否则继续判断左右子树的平衡性。
为了避免重复计算我们可以在递归时直接返回每个子树的高度。
代码实现
#include stdbool.h// 定义二叉树节点结构体
struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;
};// 计算树的高度
int height(struct TreeNode* pRoot) {if (pRoot NULL)return 0; // 空树高度为0int left height(pRoot-left); // 左子树的高度int right height(pRoot-right); // 右子树的高度if (left -1 || right -1 || abs(left - right) 1) {return -1; // 如果左右子树高度差超过1返回-1表示不平衡}return 1 (left right ? left : right); // 返回树的高度
}// 判断是否为平衡二叉树
bool IsBalanced_Solution(struct TreeNode* pRoot) {return height(pRoot) ! -1; // 如果高度返回-1表示不平衡
}代码解析 height 函数 计算二叉树的高度同时判断树是否平衡。 如果当前节点为空返回高度 0。递归计算左子树和右子树的高度。如果某个子树的高度差超过1或者某个子树本身不平衡返回 -1就返回 -1 表示树不平衡。否则返回当前树的高度。 IsBalanced_Solution 函数 通过调用 height 函数来判断整棵树是否平衡。如果 height 返回 -1则说明树不平衡返回 false否则返回 true。
时间和空间复杂度分析
时间复杂度 O(n)。每个节点只会被访问一次时间复杂度为 O(n)其中 n 是树的节点数。空间复杂度 O(h)。递归调用栈的深度是树的高度 h最坏情况下例如完全不平衡的树空间复杂度为 O(n)。
示例
示例 1
输入
{1,2,3,4,5,6,7}输出
true示例 2
输入
{}输出
true总结
本题通过递归遍历二叉树计算每个节点的左右子树高度同时判断左右子树的高度差是否超过1来判断树是否平衡。时间复杂度为 O(n)空间复杂度为 O(h)其中 n 是节点数h 是树的高度。非常难得是居然一次编译直接成功了太开心了。题刷百编其意自现。
