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 }