做的网站进不去后台,如何创建一个简单的网页,物联网今天正式开网,wordpress方小程序主题给定一个二叉树#xff0c;判断它是否是 平衡二叉树 题解#xff1a;平衡二叉树 是指该树所有节点的左右子树的深度相差不超过 1。可以采用递归遍历每一个节点#xff0c;得到其高度#xff0c;在判断高度时不可避免的要用到其左右子树的高度#xff0c;所以可以顺便判断出…给定一个二叉树判断它是否是 平衡二叉树 题解平衡二叉树 是指该树所有节点的左右子树的深度相差不超过 1。可以采用递归遍历每一个节点得到其高度在判断高度时不可避免的要用到其左右子树的高度所以可以顺便判断出左右子树的高度相差是否大于1若大于1则该节点不是平衡的整个子树也就不是平衡的。
代码如下
class Solution {
public:int GetHeight(TreeNode* cur){if(curNULL) return 0;int LeftHeight GetHeight(cur-left);if(LeftHeight-1) return -1;int RightHeight GetHeight(cur-right);if(RightHeight-1) return -1;return abs(LeftHeight- RightHeight)1? -1:1max(LeftHeight,RightHeight);}bool isBalanced(TreeNode* root) {return GetHeight(root) -1? false:true;}
}; 注意
其中对节点的左右子树高度递归判断有漏洞因为在递归的单层逻辑里对左右两个方向都做了判断所以int LeftHeight GetHeight(cur-left);这一语句是正确的判断整个左子树的情况而不是单线的左子树。
