当前位置 博文首页 > Aaron_Yang:LeetCode110: 平衡二叉树
给定一个二叉树,判断它是否是高度平衡的二叉树。
本题中,一棵高度平衡二叉树定义为:
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool isBalanced(TreeNode* root) {
return getDepth(root) == -1? false:true;
}
//返回以该节点为根节点的二叉树的高度,如果不是二叉搜索树了则返回-1
int getDepth(TreeNode *node)
{
if(node==nullptr) return 0;
int leftDepth = getDepth(node->left);
if(leftDepth == -1) return -1; //左子树已经不是二叉平衡树
int rightDepth = getDepth(node->right);
if(rightDepth == -1) return -1; //右?树已经不是?叉平衡树
int result = 0;
//中序
if(abs(leftDepth-rightDepth)>1)
result = -1;
else
{
result = 1 +max(leftDepth,rightDepth); //以当前节点作为根节点的最大高度
}
return result;
}
};
cs