- 自顶向底（暴力法，自己的解法）
先求当前节点左子树的高度depth_left，再求当前节点右子树的高度depth_right。判断当前节点是否满足平衡树的要求，如果满足递归的判断左子树和右子树。时间复杂度O(n*logn)，空间复杂度O(n)
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public://求以root为根节点的数的高，非递归的方法求解int getTreeDepth(TreeNode* root){int ans = 0;queue<TreeNode*> que;if(root != nullptr){que.push(root);}while(!que.empty()){int num = que.size();++ans;while(num --){TreeNode* temp = que.front();que.pop();if(temp -> left != nullptr){que.push(temp -> left);}if(temp -> right != nullptr){que.push(temp -> right);}} }return ans;}bool isBalanced(TreeNode* root) {if(root == nullptr) return true;int leftChildDepth = getTreeDepth(root -> left);int rightChildDepth = getTreeDepth(root -> right);if(abs(leftChildDepth - rightChildDepth) < 2){return isBalanced(root -> left) && isBalanced(root -> right);}return false;}
};
- 自底向顶（最优解）
自底向顶递归的做法类似于后序遍历，对于当前遍历到的节点，先递归地判断其左右子树是否平衡，再判断以当前节点为根的子树是否平衡。如果一棵子树是平衡的，则返回其高度（高度一定是非负整数），否则返回 ?1。如果存在一棵子树不平衡，则整个二叉树一定不平衡。时间复杂度O(n)，空间复杂度O(n)(和递归调用的层数有关)。
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public://非常巧妙的解法int getTreeDepth(TreeNode* root){if(root == nullptr) return 0;int leftChildDepth = getTreeDepth(root -> left);int rightChildDepth = getTreeDepth(root -> right);if(leftChildDepth == -1 || rightChildDepth == -1 || abs(leftChildDepth - rightChildDepth) > 1){return -1;}else{return max(leftChildDepth, rightChildDepth) + 1;}}bool isBalanced(TreeNode* root) { return getTreeDepth(root) >= 0;}
};