110.平衡二叉树（优先掌握递归）

难点：

要求每个节点的左右字数的高度相减<=1，因此，需要对每个节点都进行检查，难就难在怎么获得任意节点的高度

其中递归是最简单的：

 1 int isB_cursor(TreeNode* node, bool &isBalance)
 2 {
 3     if (isBalance == false) return 0;
 4     if (!node) return 0;
 5     
 6     int leftLength = isB_cursor(node->left, isBalance);
 7     int rightLength = isB_cursor(node->right, isBalance);
 8 
 9     if (abs(leftLength - rightLength) > 1)
10     {
11         isBalance = false;
12     }
13 
14     return 1 + max(leftLength, rightLength);
15 }
16 bool isBalanced_cursor(TreeNode* root) {
17     bool result = true;
18     if (!root) return result;
19     isB_cursor(root, result);
20 
21     return result;
22 }

迭代法，很难

有两个方案获得任意节点的高度，一个是使用层序遍历

另一个很难，先弹出去当前节点，然后在押入，同时压进去左右孩子，类似一路到底，然后在回溯，回溯的时候-1，

用NULL来分开当前节点和左右孩子的分界线：

代码：

 1 int getMaxHeight(TreeNode* node)
 2 {
 3     if (!node) return 0;
 4 
 5     int result = 0;
 6     int depth = 0;
 7     stack<TreeNode*> selected;
 8     selected.push(node);
 9     while (!selected.empty())
10     {
11         TreeNode* cur_ = selected.top();
12         selected.pop();
13         if (cur_)
14         {
15             //先把自己压进去，然后压进去左右孩子，
16             selected.push(cur_);
17             selected.push(NULL);//代表是下一个了
18 
19             if (cur_->left) selected.push(cur_->left);
20             if (cur_->right)selected.push(cur_->right);
21 
22             depth++;
23         }
24         else
25         {
26             selected.pop();
27             depth--;
28         }
29         result = result > depth ? result : depth;
30     }
31 
32     return result;
33 }
34 
35 //先看每一个节点
36 bool isBalanced(TreeNode* root) {
37     bool result = true;
38     if (!root) return result;
39 
40     stack<TreeNode*> selected;
41     selected.push(root);
42 
43     while (!selected.empty())
44     {
45         auto cur_ = selected.top();
46         selected.pop();
47 
48         int leftLength = getMaxHeight(cur_->left);
49         int rightLength = getMaxHeight(cur_->right);
50 
51         if (abs(leftLength - rightLength) > 1)
52             return false;
53 
54         if (cur_->left) selected.push(cur_->left);
55         if (cur_->right) selected.push(cur_->right);
56     }
57 
58     return result;
59 }