110.平衡二叉树
个人记忆口诀：高度就是把这棵树放在地面上，叶子节点接触地面。看成叶子结点距离地面最近，按照高楼的思路来计数的话，叶子节点是一楼，所以高度是1。依次网上面是二楼，三楼等等，因此高度就是2，3 等等。
深度就是像植物的根系一样，往下扎根，所以把根结点看作是从地下网上靠近的植物的根。越往上就说明这个根扎的越不深，因此深度最低，就只是一。越往下说明扎的越深，因此深度依次增加，为2，3等等
卡哥说，递归的话，用后序遍历求高度，，因为左右中的顺序能很好地将子节点的信息，例如高度返回给子树的根结点，然后该根节点再根据两个高度信息进行操作了。必须知道左右子树的高度信息，才能对该根节点的进行操作的情况我们就要用递归的后序遍历。
用前序遍历求深度，因为中左右的顺序像是往下探索，左和右在中之后，就可以将中的信息传给左和右了。
迭代法在网站上，没时间看，有空再看
后序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
int getHeight(TreeNode *root) {
if (root == NULL) return 0;
int l = getHeight(root->left);
if (l == -1) return -1;
int r = getHeight(root->right);
if (r == -1) return -1;
if (fabs(l - r) > 1) return -1;
else {
int result = 1 + max(l, r);
return result;
}
}
bool isBalanced(TreeNode* root) {
if(getHeight(root) == -1) return false;
else return true;
}
};
|
待补充的内容
257. 二叉树的所有路径
选择前序遍历，因为只有中左右的顺序，才能让根节点指向他的左右子树的结点
递归和回溯是相辅相成的，，只要有递归就一定回溯
看了卡哥的几乎是照着抄的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| class Solution {
public:
void traversal(TreeNode *node, vector<int> &path, vector<string> &result) {
path.push_back(node->val);
if (!node->left && !node->right) {
string sPath;
int i;
for (i = 0; i < path.size() - 1; i++) {
sPath += to_string(path[i]);
sPath += "->";
}
sPath += to_string(path[i]);
result.push_back(sPath);
return;
}
if (node->left) {
traversal(node->left, path, result);
path.pop_back();
}
if (node->right) {
traversal(node->right, path, result);
path.pop_back();
}
}
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> result;
vector<int> path;
traversal(root, path, result);
return result;
}
};
|
左叶子结点定义：父节点的左孩子，同时该结点是叶子节点，而不是靠左边的叶子结点
用后序遍历，，把左右子树的数值相加，得到总值
