Leetcode -110.平衡二叉树 -226.翻转二叉树
Leetcode -110.平衡二叉树
题目:给定一个二叉树,判断它是否是高度平衡的二叉树。
本题中,一棵高度平衡二叉树定义为:
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 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] 内
- 10^4 <= Node.val <= 10^4
思路:化为子问题计算每颗子树的左右子树高度;结束条件为子树的左右子树高度差大于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);
}
Leetcode -226.翻转二叉树
题目:给你一棵二叉树的根节点 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] 内
- 100 <= Node.val <= 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;
}
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhggiccb
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
怎样阻止微信小程序自动打开
PHP中文网 06-13