leetode110_平衡二叉树

一.  肯定递归啦.....

#include
#include
#include
using namespace std;struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};class Solution {
public:int depth(TreeNode* root) {if (root &＃61;&＃61; NULL) return 0;return max(depth(root->left), depth(root->right)) &＃43; 1;}bool isBalanced(TreeNode* root) {//考虑最简单的情况,即树为空,肯定为true.if (root &＃61;&＃61; NULL) return true;//先判断当前节点左右子树符合不符合要求.int leftD &＃61; depth(root->left);int rightD &＃61; depth(root->right);if (abs(leftD - rightD) > 1) return false;//再判断左子树和右子树分别符不符合.return isBalanced(root->left) && isBalanced(root->right);}
};

1. 进行了剪枝, 当高度差大于1时,直接false,省去了后面的计算.但其实效率还是不高,因为我们每经过一个节点,就算高度, 很费时间.

2. 将高度与判断融合, 在计算高度的同时判断是否符合,时间复杂度为O(N).

//自底向上
class Solution {
public:bool res &＃61; true;int helper(TreeNode* root) {if (root &＃61;&＃61; NULL) return 0;int left &＃61; helper(root->left);int right &＃61; helper(root->right);//计算节点的高度的同时判断.if (abs(left - right) > 1) {res &＃61; false;//如果为false,直接返回即可,就不用判断了.return 0;}return max(left, right) &＃43; 1;}bool isBalanced(TreeNode* root) {int tmp &＃61; helper(root);return res;}
};