剑指Offer JZ39 平衡二叉树 C++实现

题目描述

输入一棵二叉树，判断该二叉树是否是平衡二叉树。

在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树

解题思路

方法一：

1、思路：平衡二叉树的任意结点的子树的高度差都小于等于1，在上一题的方法三中，我们通过分治法递归地求左右子树的深度以得到当前结点的深度，在此题中只需要在方法三的递归回溯时加上一条判断语句来判断当前左右子树的高度差是否大于1即可。

2、代码：

class Solution {
public:int isBalanced(TreeNode *root, bool &flag) {if (!root) return 0;int lval = isBalanced(root->left, flag);int rval = isBalanced(root->right, flag);if (abs(lval - rval) > 1) flag = false;return max(lval, rval) + 1;}bool IsBalanced_Solution(TreeNode* pRoot) {if (!pRoot) return true;bool flag = true;isBalanced(pRoot, flag);return flag;}
};

3、复杂度：

时间复杂度：O(n)；

空间复杂度：O(1)。