1+ #二叉树：以为使用了递归，其实还隐藏着回溯
12
2- 在上一面
3+ > 补充一波
34
5+ 昨天的总结篇中[ 还在玩耍的你，该总结啦！（本周小结之二叉树）] ( https://mp.weixin.qq.com/s/QMBUTYnoaNfsVHlUADEzKg ) ，有两处问题需要说明一波。
6+
7+ ##求相同的树
8+
9+ [ 还在玩耍的你，该总结啦！（本周小结之二叉树）] ( https://mp.weixin.qq.com/s/QMBUTYnoaNfsVHlUADEzKg ) 中求100.相同的树的代码中，我笔误贴出了 求对称树的代码了，细心的同学应该都发现了。
10+
11+ 那么如下我再给出求100. 相同的树 的代码，如下：
12+
13+ ```
14+ class Solution {
15+ public:
16+ bool compare(TreeNode* tree1, TreeNode* tree2) {
17+ if (tree1 == NULL && tree2 != NULL) return false;
18+ else if (tree1 != NULL && tree2 == NULL) return false;
19+ else if (tree1 == NULL && tree2 == NULL) return true;
20+ else if (tree1->val != tree2->val) return false; // 注意这里我没有使用else
21+
22+ // 此时就是：左右节点都不为空，且数值相同的情况
23+ // 此时才做递归，做下一层的判断
24+ bool compareLeft = compare(tree1->left, tree2->left); // 左子树：左、 右子树：左
25+ bool compareRight = compare(tree1->right, tree2->right); // 左子树：右、 右子树：右
26+ bool isSame = compareLeft && compareRight; // 左子树：中、 右子树：中（逻辑处理）
27+ return isSame;
28+
29+ }
30+ bool isSameTree(TreeNode* p, TreeNode* q) {
31+ return compare(p, q);
32+ }
33+ };
34+ ```
35+
36+ 以上的代码相对于：[ 二叉树：我对称么？] ( https://mp.weixin.qq.com/s/Kgf0gjvlDlNDfKIH2b1Oxg ) 仅仅修改了变量的名字（为了符合判断相同树的语境）和 遍历的顺序。
37+
38+ 大家应该会体会到：** 认清[ 判断对称树] ( https://mp.weixin.qq.com/s/Kgf0gjvlDlNDfKIH2b1Oxg ) 本质之后， 对称树的代码 稍作修改 就可以直接用来AC 100.相同的树。**
39+
40+ ##递归中隐藏着回溯
41+
42+ 在[ 二叉树：找我的所有路径？] ( https://mp.weixin.qq.com/s/Osw4LQD2xVUnCJ-9jrYxJA ) 中我强调了本题其实是用到了回溯的，并且给出了第一个版本的代码，把回溯的过程充分的提现了出来。
43+
44+ 如下的代码充分的体现出回溯：(257. 二叉树的所有路径)
445
546```
647class Solution {
748private:
8- void traversal(TreeNode* cur, string path, vector<string>& result) {
9- path += to_string(cur->val); // 中
49+
50+ void traversal(TreeNode* cur, vector<int>& path, vector<string>& result) {
51+ path.push_back(cur->val);
52+ // 这才到了叶子节点
1053 if (cur->left == NULL && cur->right == NULL) {
11- result.push_back(path);
54+ string sPath;
55+ for (int i = 0; i < path.size() - 1; i++) {
56+ sPath += to_string(path[i]);
57+ sPath += "->";
58+ }
59+ sPath += to_string(path[path.size() - 1]);
60+ result.push_back(sPath);
1261 return;
1362 }
14-
1563 if (cur->left) {
16- path += "->";
17- traversal(cur->left, path, result); // 左
64+ traversal(cur->left, path, result);
1865 path.pop_back(); // 回溯
19- path.pop_back();
2066 }
2167 if (cur->right) {
22- path += "->";
23- traversal(cur->right, path, result); // 右
68+ traversal(cur->right, path, result);
2469 path.pop_back(); // 回溯
25- path.pop_back();
2670 }
2771 }
2872
2973public:
3074 vector<string> binaryTreePaths(TreeNode* root) {
3175 vector<string> result;
32- string path;
76+ vector<int> path;
3377 if (root == NULL) return result;
3478 traversal(root, path, result);
3579 return result;
36-
3780 }
3881};
3982```
4083
41- 没有回溯了
84+
85+ 如下为精简之后的递归代码：(257. 二叉树的所有路径)
4286```
4387class Solution {
4488private:
@@ -48,15 +92,8 @@ private:
4892 result.push_back(path);
4993 return;
5094 }
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- }
95+ if (cur->left) traversal(cur->left, path + "->", result); // 左 回溯就隐藏在这里
96+ if (cur->right) traversal(cur->right, path + "->", result); // 右 回溯就隐藏在这里
6097 }
6198
6299public:
@@ -66,7 +103,61 @@ public:
66103 if (root == NULL) return result;
67104 traversal(root, path, result);
68105 return result;
69-
70106 }
71107};
72108```
109+
110+ 上面的代码，大家貌似感受不到回溯了，其实** 回溯就隐藏在traversal(cur->left, path + "->", result);中的 path + "->"。 每次函数调用完，path依然是没有加上"->" 的，这就是回溯了。**
111+
112+ 为了把这份精简代码的回溯过程展现出来，大家可以试一试把：
113+
114+ ```
115+ if (cur->left) traversal(cur->left, path + "->", result); // 左 回溯就隐藏在这里
116+ ```
117+
118+ 改成如下代码：
119+
120+ ```
121+ path += "->";
122+ traversal(cur->left, path, result); // 左
123+ ```
124+
125+ 即：
126+
127+ ```
128+
129+ if (cur->left) {
130+ path += "->";
131+ traversal(cur->left, path, result); // 左
132+ }
133+ if (cur->right) {
134+ path += "->";
135+ traversal(cur->right, path, result); // 右
136+ }
137+ ```
138+
139+ 此时就没有回溯了，这个代码就是通过不了的了。
140+
141+ 如果想把回溯加上，就要 在上面代码的基础上，加上回溯，就可以AC了。
142+
143+ ```
144+ if (cur->left) {
145+ path += "->";
146+ traversal(cur->left, path, result); // 左
147+ path.pop_back(); // 回溯
148+ path.pop_back();
149+ }
150+ if (cur->right) {
151+ path += "->";
152+ traversal(cur->right, path, result); // 右
153+ path.pop_back(); // 回溯
154+ path.pop_back();
155+ }
156+ ```
157+
158+ ** 大家应该可以感受出来，如果把` path + "->" ` 作为函数参数就是可以的，因为并有没有改变path的数值，执行完递归函数之后，path依然是之前的数值（相当于回溯了）**
159+
160+ 如果有点遗忘了，建议把这篇[ 二叉树：找我的所有路径？] ( https://mp.weixin.qq.com/s/Osw4LQD2xVUnCJ-9jrYxJA ) 在仔细看一下，然后再看这里的总结，相信会豁然开朗。
161+
162+ 这里我尽量把逻辑的每一个细节都抠出来展现了，希望对大家有所帮助！
163+