pc端网站开发技术搜狗站长工具

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

思路一：递归

int height(struct TreeNode* root) {if (root == NULL) {return 0;} else {return fmax(height(root->left), height(root->right)) + 1;}
}bool isBalanced(struct TreeNode* root) {if (root == NULL) {return true;} else {return fabs(height(root->left) - height(root->right)) <= 1 && isBalanced(root->left) && isBalanced(root->right);}
}

 分析：

本题要判断是否为平衡二叉树，利用height函数求得二叉树左右子树深度值，再递归判断两个子树高度差是否大于一得到答案

总结：

本题为对二叉树高度差的操作，理清左右子树关系，利用递归即可得到答案