这道题比较考验思维. 平衡二叉树的条件是左, 右子树的深度差不大于 1, 所以我们首先需要计算出二叉树的深度. 而这道题需要返回的并不是深度, 而是一个布尔值, 因此我们初始认为这棵树是平衡的, 在计算深度的过程中, 如果发现左, 右子树的深度大于 1 了, 就将答案置为 false.
计算深度我们应该另开一个函数进行递归操作, 一棵树的深度是它的左子树和右子树这两者中最大的子树深度 + 1. 递归计算左子树的深度和右子树的深度, 返回的是整棵树的深度, 在计算左, 右子树深度的过程中, 如果发现深度差大于 1, 就将答案置为 false.
c++ 代码如下:
- class Solution {
- public:
- bool ans = true;
- bool IsBalanced_Solution(TreeNode* pRoot) {
- dfs(pRoot);
- return ans;
- }
- int dfs(TreeNode* pRoot){
- if(!pRoot) return 0;
- int left = dfs(pRoot->left);
- int right = dfs(pRoot->right);
- if(abs(left - right)> 1) ans = false;
- return max(left, right) + 1;
- }
- };
平衡二叉树
来源: http://www.bubuko.com/infodetail-3345995.html