深圳网站设计推荐柚米,做自媒体怎么在其它网站搬运内容,怎么用自己的电脑做服务器发布网站,个人简介网页制作力扣网 110 平衡二叉树
题目描述
给定一个二叉树#xff0c;判断它是否是高度平衡的二叉树。
本题中#xff0c;一棵高度平衡二叉树定义为#xff1a; 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。 示例 1#xff1a; 输入#xff1a;root [3,9,20,…力扣网 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] 内-104 Node.val 104
思路分析
知识点递归、二叉树
思路解析
找出左右子树的高度如果高度差出现大于一的情况就返回false从根节点开始先从左子树找再去右子树找
这里为了方便判断左右子树高度大小利用了假设法先假设左子树高度最高后面再判断一下如果不对就换一下。
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/int BinaryTreeHight(struct TreeNode* root)//求二叉树高度
{if (root NULL){return 0;}return fmax(BinaryTreeHight(root-left), BinaryTreeHight(root-right)) 1;}
bool isBalanced(struct TreeNode* root) {if(rootNULL){return true;}int leftBinaryTreeHight(root-left);//保存左子树高度int rightBinaryTreeHight(root-right);//保存右子树高度int maxleft;//假设法int minright;if(leftright){minleft;maxright;}if((max-min)1){return false;}return isBalanced(root-left)isBalanced(root-right);}
