wordpress做出影视网站,2017优秀网站设计,关于设计网站,免费背景图片素材网题目#xff1a;
实现一个函数#xff0c;检查二叉树是否平衡。在这个问题中#xff0c;平衡树的定义如下#xff1a;任意一个节点#xff0c;其两棵子树的高度差不超过 1。
示例 1#xff1a;
给定二叉树 [3,9,20,null,null,15,7]3/ \9 20/ \15 7
返回 true 。
…题目
实现一个函数检查二叉树是否平衡。在这个问题中平衡树的定义如下任意一个节点其两棵子树的高度差不超过 1。
示例 1
给定二叉树 [3,9,20,null,null,15,7]3/ \9 20/ \15 7
返回 true 。
示例 2
给定二叉树 [1,2,2,3,3,null,null,4,4]1/ \2 2/ \3 3/ \
4 4
返回 false 。
思路
采用递归的方法检查每个节点的左右子树的高度差是否不超过1。一旦有任何一个节点不满足平衡二叉树的条件那么整个二叉树一定不是平衡二叉树。采用类似后序遍历的方法先检查左子树的节点再检查右子树的节点最后是根。递归计算直到计算完整个树。
C代码如下
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/int GetHeight(struct TreeNode* root){if(root NULL) return 0;int LeftHeight GetHeight(root - left);if(LeftHeight -1) return -1;int RightHeight GetHeight(root - right);if(RightHeight -1) return -1;if(fabs(LeftHeight - RightHeight) 1){return -1;}else{return fmax(LeftHeight, RightHeight) 1;}
}bool isBalanced(struct TreeNode* root) {return GetHeight(root) 0;
}
