Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit9eea30c

Browse files
Update
1 parent210390c commit9eea30c

File tree

6 files changed

+184
-35
lines changed

6 files changed

+184
-35
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -94,6 +94,7 @@
9494
*[二叉树：我有多少个节点？](https://mp.weixin.qq.com/s/2_eAjzw-D0va9y4RJgSmXw)
9595
*[二叉树：我平衡么？](https://mp.weixin.qq.com/s/isUS-0HDYknmC0Rr4R8mww)
9696
*[二叉树：找我的所有路径？](https://mp.weixin.qq.com/s/Osw4LQD2xVUnCJ-9jrYxJA)
97+
*[还在玩耍的你，该总结啦！（本周小结之二叉树）](https://mp.weixin.qq.com/s/QMBUTYnoaNfsVHlUADEzKg)
9798

9899

99100
（持续更新中....）

‎pics/404.左叶子之和1.png

21.9 KB
Loading

‎problems/0100.相同的树.md

Lines changed: 14 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -68,40 +68,38 @@ else if (tree1->val != tree2->val) return false; // 注意这里我没有
6868
代码如下：
6969

7070
```
71-
bool outside = compare(tree1->left, tree2->right); // 左子树：左、 右子树：左
72-
bool inside = compare(tree1->right, tree2->left); // 左子树：右、 右子树：右
71+
bool outside = compare(tree1->left, tree2->left); // 左子树：左、 右子树：左
72+
bool inside = compare(tree1->right, tree2->right); // 左子树：右、 右子树：右
7373
bool isSame = outside && inside; // 左子树：中、 右子树：中（逻辑处理）
7474
return isSame;
7575
```
76-
-------------------------------------------------------------- 写到这
7776
最后递归的C++整体代码如下：
7877

7978
```
8079
class Solution {
8180
public:
82-
bool compare(TreeNode* left, TreeNode* right) {
83-
// 首先排除空节点的情况
84-
if (left == NULL && right != NULL) return false;
85-
else if (left != NULL && right == NULL) return false;
86-
else if (left == NULL && right == NULL) return true;
87-
// 排除了空节点，再排除数值不相同的情况
88-
else if (left->val != right->val) return false;
81+
bool compare(TreeNode* tree1, TreeNode* tree2) {
82+
if (tree1 == NULL && tree2 != NULL) return false;
83+
else if (tree1 != NULL && tree2 == NULL) return false;
84+
else if (tree1 == NULL && tree2 == NULL) return true;
85+
else if (tree1->val != tree2->val) return false; // 注意这里我没有使用else
8986
9087
// 此时就是：左右节点都不为空，且数值相同的情况
9188
// 此时才做递归，做下一层的判断
92-
bool outside = compare(left->left, right->right); // 左子树：左、 右子树：左
93-
bool inside = compare(left->right, right->left); // 左子树：右、 右子树：右
94-
bool isSame = outside && inside; // 左子树：中、 右子树：中（逻辑处理）
89+
bool outside = compare(tree1->left, tree2->left); // 左子树：左、 右子树：左
90+
bool inside = compare(tree1->right, tree2->right); // 左子树：右、 右子树：右
91+
bool isSame = outside && inside; // 左子树：中、 右子树：中（逻辑处理）
9592
return isSame;
9693
9794
}
98-
bool isSymmetric(TreeNode* root) {
99-
if (root == NULL) return true;
100-
return compare(root->left, root->right);
95+
bool isSameTree(TreeNode* p, TreeNode* q) {
96+
return compare(p, q);
10197
}
10298
};
10399
```
104100

101+
-------------------------------------------------------------- 写到这
102+
105103
**我给出的代码并不简洁，但是把每一步判断的逻辑都清楚的描绘出来了。**
106104

107105
如果上来就看网上各种简洁的代码，看起来真的很简单，但是很多逻辑都掩盖掉了，而题解可能也没有把掩盖掉的逻辑说清楚。

‎problems/0257.二叉树的所有路径.md

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -207,8 +207,12 @@ public:
207207

208208
那么在如上代码中，**貌似没有看到回溯的逻辑，其实不然，回溯就隐藏在`traversal(cur->left, path + "->", result);`中的`path + "->"`。** 每次函数调用完，path依然是没有加上"->" 的，这就是回溯了。
209209

210+
211+
210212
**综合以上，第二种递归的代码虽然精简但把很多重要的点隐藏在了代码细节里，第一种递归写法虽然代码多一些，但是把每一个逻辑处理都完整的展现了出来了。**
211213

214+
215+
212216
##迭代法
213217

214218
至于非递归的方式，我们可以依然可以使用前序遍历的迭代方式来模拟遍历路径的过程，对该迭代方式不了解的同学，可以看文章[二叉树：听说递归能做的，栈也能做！](https://mp.weixin.qq.com/s/c_zCrGHIVlBjUH_hJtghCg)和[二叉树：前中后序迭代方式的写法就不能统一一下么？](https://mp.weixin.qq.com/s/WKg0Ty1_3SZkztpHubZPRg)。

‎problems/0404.左叶子之和.md

Lines changed: 93 additions & 19 deletions
Original file line numberDiff line numberDiff line change
@@ -1,9 +1,19 @@
11
##题目地址
22
https://leetcode-cn.com/problems/sum-of-left-leaves/
33

4-
##思路
4+
>有的题目就是
55
6-
首先要注意是判断左叶子呢，不是左子树，不要上来想着层序遍历。
6+
#404.左叶子之和
7+
8+
计算给定二叉树的所有左叶子之和。
9+
10+
示例：
11+
12+
<imgsrc='../pics/404.左叶子之和1.png'width=600> </img></div>
13+
14+
#思路
15+
16+
**首先要注意是判断左叶子，不是二叉树左侧节点，所以不要上来想着层序遍历。**
717

818
因为题目中其实没有说清楚左叶子究竟是什么节点，那么我来给出左叶子的明确定义：**如果左节点不为空，且左节点没有左右孩子，那么这个节点就是左叶子**
919

@@ -13,42 +23,99 @@ https://leetcode-cn.com/problems/sum-of-left-leaves/
1323

1424
**其实是0，因为这棵树根本没有左叶子！**
1525

16-
那么判断左叶子，如果**判断当前节点是不是左叶子是无法判断的，必须要通过节点的父节点来判断其左孩子是不是左叶子。**
26+
那么**判断当前节点是不是左叶子是无法判断的，必须要通过节点的父节点来判断其左孩子是不是左叶子。**
27+
1728

18-
判断的根据如下：
29+
如果该节点的左节点不为空，该节点的左节点的左节点为空，该节点的左节点的右节点为空，则找到了一个左叶子，判断代码如下：
1930

2031
```
21-
if (node->left != NULL && node->left->left == NULL && node->left->right == NULL) {
22-
sum = node->left->val;
23-
}
32+
if (node->left != NULL && node->left->left == NULL && node->left->right == NULL) {
33+
左叶子节点处理逻辑
34+
}
35+
```
36+
37+
##递归法
38+
39+
递归的遍历顺序为后序遍历（左右中），是因为要通过递归函数的返回值来累加求取左叶子数值之和。。
40+
41+
递归三部曲：
42+
43+
1. 确定递归函数的参数和返回值
44+
45+
判断一个树的左叶子节点之和，那么一定要传入树的根节点，递归函数的返回值为数值之和，所以为int
46+
47+
使用题目中给出的函数就可以了。
48+
49+
2. 确定终止条件
50+
51+
依然是
52+
```
53+
if (root == NULL) return 0;
54+
```
55+
56+
3. 确定单层递归的逻辑
57+
58+
当遇到左叶子节点的时候，记录数值，然后通过递归求取左子树左叶子之和，和 右子树左叶子之和，相加便是整个树的左叶子之和。
59+
60+
代码如下：
61+
62+
```
63+
int leftValue = sumOfLeftLeaves(root->left); // 左
64+
int rightValue = sumOfLeftLeaves(root->right); // 右
65+
// 中
66+
int midValue = 0;
67+
if (root->left && !root->left->left && !root->left->right) {
68+
midValue = root->left->val;
69+
}
70+
int sum = midValue + leftValue + rightValue;
71+
return sum;
72+
2473
```
2574

26-
递归写法代码如下：
2775

28-
##递归C++代码
76+
整体递归代码如下：
2977

3078
```
3179
class Solution {
3280
public:
3381
int sumOfLeftLeaves(TreeNode* root) {
3482
if (root == NULL) return 0;
35-
int sum = 0;
83+
84+
int leftValue = sumOfLeftLeaves(root->left); // 左
85+
int rightValue = sumOfLeftLeaves(root->right); // 右
86+
// 中
87+
int midValue = 0;
88+
if (root->left && !root->left->left && !root->left->right) { // 中
89+
midValue = root->left->val;
90+
}
91+
int sum = midValue + leftValue + rightValue;
92+
return sum;
93+
}
94+
};
95+
```
96+
97+
以上代码精简之后如下：
98+
99+
```
100+
class Solution {
101+
public:
102+
int sumOfLeftLeaves(TreeNode* root) {
103+
if (root == NULL) return 0;
104+
int midValue = 0;
36105
if (root->left != NULL && root->left->left == NULL && root->left->right == NULL) {
37-
sum = root->left->val;
106+
midValue = root->left->val;
38107
}
39-
returnsum + sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);
108+
returnmidValue + sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);
40109
}
41110
};
42111
```
43112

44-
递归的过程其实就是二叉树的前序遍历，那么写过二叉树的同学都知道，既然是二叉树的前序遍历，能写出递归，就能写出非递归。
113+
##迭代法
45114

46-
如果对二叉树的各种递归和非递归的写法不熟悉，可以看我的这个题解：
47-
[彻底吃透二叉树的前中后序递归法和迭代法！！](https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/che-di-chi-tou-er-cha-shu-de-qian-zhong-hou-xu-d-2/)
48115

49-
那么非递归版本善良登场，判断条件都是一样的
116+
本题使用了后序遍历啊，那么参考文章[二叉树：听说递归能做的，栈也能做！](https://mp.weixin.qq.com/s/c_zCrGHIVlBjUH_hJtghCg)和[二叉树：前中后序迭代方式的写法就不能统一一下么？](https://mp.weixin.qq.com/s/WKg0Ty1_3SZkztpHubZPRg)中的写法，同样可以写出一个后序遍历的迭代法。
50117

51-
##非递归C++代码
118+
判断条件都是一样的，代码如下：
52119

53120
```
54121
@@ -70,8 +137,15 @@ public:
70137
}
71138
return result;
72139
}
73-
74-
75140
};
76141
```
77142

143+
#总结
144+
145+
这道题目要求左叶子之和，其实是比较绕的，因为不能判断本节点是不是左叶子节点。
146+
147+
此时就要通过节点的父节点来判断其左孩子是不是左叶子了。
148+
149+
**平时我们解二叉树的题目时，已经习惯了通过节点的左右孩子判断本节点的属性，而本题我们要通过节点的父节点判断本节点的属性。**
150+
151+
希望通过这道题目，可以扩展大家对二叉树的解题思路。
Lines changed: 72 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,72 @@
1+
2+
在上一面
3+
4+
5+
```
6+
class Solution {
7+
private:
8+
void traversal(TreeNode* cur, string path, vector<string>& result) {
9+
path += to_string(cur->val); // 中
10+
if (cur->left == NULL && cur->right == NULL) {
11+
result.push_back(path);
12+
return;
13+
}
14+
15+
if (cur->left) {
16+
path += "->";
17+
traversal(cur->left, path, result); // 左
18+
path.pop_back(); // 回溯
19+
path.pop_back();
20+
}
21+
if (cur->right) {
22+
path += "->";
23+
traversal(cur->right, path, result); // 右
24+
path.pop_back(); // 回溯
25+
path.pop_back();
26+
}
27+
}
28+
29+
public:
30+
vector<string> binaryTreePaths(TreeNode* root) {
31+
vector<string> result;
32+
string path;
33+
if (root == NULL) return result;
34+
traversal(root, path, result);
35+
return result;
36+
37+
}
38+
};
39+
```
40+
41+
没有回溯了
42+
```
43+
class Solution {
44+
private:
45+
void traversal(TreeNode* cur, string path, vector<string>& result) {
46+
path += to_string(cur->val); // 中
47+
if (cur->left == NULL && cur->right == NULL) {
48+
result.push_back(path);
49+
return;
50+
}
51+
52+
if (cur->left) {
53+
path += "->";
54+
traversal(cur->left, path, result); // 左
55+
}
56+
if (cur->right) {
57+
path += "->";
58+
traversal(cur->right, path, result); // 右
59+
}
60+
}
61+
62+
public:
63+
vector<string> binaryTreePaths(TreeNode* root) {
64+
vector<string> result;
65+
string path;
66+
if (root == NULL) return result;
67+
traversal(root, path, result);
68+
return result;
69+
70+
}
71+
};
72+
```

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp