题目:给定一个二叉树,判断它是否是高度平衡的二叉树。
本题中,一棵高度平衡二叉树定义为: 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
示例 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] 内
思路:化为子问题计算每颗子树的左右子树高度;结束条件为子树的左右子树高度差大于1;
//计算子树的高度
int TreeHeight(struct TreeNode* root)
{
if (root == NULL)
return 0;
int h1 = TreeHeight(root->left) + 1;
int h2 = TreeHeight(root->right) + 1;
//返回深度较高的
return h1 > h2 ? h1 : h2;
}
bool isBalanced(struct TreeNode* root)
{
if (root == NULL)
return true;
//判断当前根的左右子树高度差是否大于1
if (abs(TreeHeight(root->left) - TreeHeight(root->right)) > 1)
return false;
//如果当前根左右子树高度差小于等于1,递归其左子树的根和右子树的根进行判断
return isBalanced(root->left) && isBalanced(root->right);
}
题目:给你一棵二叉树的根节点 root ,翻转这棵二叉树,并返回其根节点。
示例 1:
输入:root = [4, 2, 7, 1, 3, 6, 9] 输出:[4, 7, 2, 9, 6, 3, 1]
示例 2: 输入:root = [2, 1, 3] 输出:[2, 3, 1]
示例 3: 输入:root = [] 输出:[]
提示: 树中节点数目范围在[0, 100] 内
思路:化为子问题左根的左指针指向右根的右指针,右根的右指针指向左根的左指针;左根的右指针指向右根的左指针,右根的左指针指向左根的右指针;结束条件为空;
struct TreeNode* invertTree(struct TreeNode* root)
{
if (root == NULL)
return NULL;
//将当前左根和右根记录下来
struct TreeNode* LeftRoot = invertTree(root->left);
struct TreeNode* RightRoot = invertTree(root->right);
//根的左右子树交换
root->left = RightRoot;
root->right = LeftRoot;
return root;
}