11
2- ##C++代码递归
2+ > 我的左下角的数值是多少?
3+
4+ #513.找树左下角的值
5+
6+ 给定一个二叉树，在树的最后一行找到最左边的值。
7+
8+ 示例 1:
9+
10+ <img src =' ../pics/513.找树左下角的值.png ' width =600 > </img ></div >
11+
12+ 示例 2:
13+
14+ <img src =' ../pics/513.找树左下角的值1.png ' width =600 > </img ></div >
15+
16+ #思路
17+
18+ 本地要找出树的最后一行找到最左边的值。此时大家应该想起用层序遍历是非常简单的了，反而用递归的话会比较难一点。
19+
20+ 我们依然还是先介绍递归法。
21+
22+ ##递归
23+
24+ 咋眼一看，这道题目用递归的话就就一直向左遍历，最后一个就是答案呗？
25+
26+ 没有这么简单，一直向左遍历到最后一个，它未必是最后一行啊。
27+
28+ 我们来分析一下题目：在树的** 最后一行** 找到** 最左边的值** 。
29+
30+ 首先要是最后一行，然后是最左边的值。
31+
32+ 如果使用递归法，如何判断是最后一行呢，其实就是深度最大的叶子节点一定是最后一行。
33+
34+ 如果对二叉树深度和高度还有点疑惑的话，请看：[ 二叉树：我平衡么？] ( https://mp.weixin.qq.com/s/isUS-0HDYknmC0Rr4R8mww ) 。
35+
36+ 所以要找深度最大的叶子节点。
37+
38+ 那么如果找最左边的呢？可以使用前序遍历，这样才先优先左边搜索，然后记录深度最大的叶子节点，此时就是树的最后一行最左边的值。
39+
40+ 递归三部曲：
41+
42+ 1 . 确定递归函数的参数和返回值
43+
44+ 参数必须有要遍历的树的根节点，还有就是一个int型的变量用来记录最长深度。 这里就不需要返回值了，所以递归函数的返回类型为void。
45+
46+ 本题还需要类里的两个全局变量，maxLen用来记录最大深度，maxleftValue记录最大深度最左节点的数值。
47+
48+ 代码如下：
49+
50+ ```
51+ int maxLen = INT_MIN; // 全局变量 记录最大深度
52+ int maxleftValue; // 全局变量 最大深度最左节点的数值
53+ void traversal(TreeNode* root, int leftLen)
54+ ```
55+
56+ 有的同学可能疑惑，为啥不能递归函数的返回值返回最长深度呢？
57+
58+ 其实很多同学都对递归函数什么时候要有返回值，什么时候不能有返回值很迷茫。
59+
60+ ** 如果需要遍历整颗树，递归函数就不能有返回值。如果需要遍历某一条固定路线，递归函数就一定要有返回值！**
61+
62+ 初学者可能对这个结论不太理解，别急，后面我会安排一道题目专门讲递归函数的返回值问题。这里大家暂时先了解一下。
63+
64+ 本题我们是要遍历整个树找到最深的叶子节点，需要遍历整颗树，所以递归函数没有返回值。
65+
66+ 2 . 确定终止条件
67+
68+ 当遇到叶子节点的时候，就需要统计一下最大的深度了，所以需要遇到叶子节点来更新最大深度。
69+
70+ 代码如下：
71+
72+ ```
73+ if (root->left == NULL && root->right == NULL) {
74+ if (leftLen > maxLen) {
75+ maxLen = leftLen; // 更新最大深度
76+ maxleftValue = root->val; // 最大深度最左面的数值
77+ }
78+ return;
79+ }
80+ ```
81+
82+ 3 . 确定单层递归的逻辑
83+
84+ 在找最大深度的时候，递归的过程中依然要使用回溯，代码如下：
85+
86+ ```
87+ // 中
88+ if (root->left) { // 左
89+ leftLen++; // 深度加一
90+ traversal(root->left, leftLen);
91+ leftLen--; // 回溯，深度减一
92+ }
93+ if (root->right) { // 右
94+ leftLen++; // 深度加一
95+ traversal(root->right, leftLen);
96+ leftLen--; // 回溯，深度减一
97+ }
98+ return;
99+ ```
100+
101+ 完整代码如下：
3102
4103```
5104class Solution {
@@ -9,20 +108,20 @@ public:
9108 void traversal(TreeNode* root, int leftLen) {
10109 if (root->left == NULL && root->right == NULL) {
11110 if (leftLen > maxLen) {
12- maxleftValue = root->val;
13111 maxLen = leftLen;
112+ maxleftValue = root->val;
14113 }
15114 return;
16115 }
17116 if (root->left) {
18117 leftLen++;
19118 traversal(root->left, leftLen);
20- leftLen--;
119+ leftLen--; // 回溯
21120 }
22121 if (root->right) {
23122 leftLen++;
24123 traversal(root->right, leftLen);
25- leftLen--;
124+ leftLen--; // 回溯
26125 }
27126 return;
28127 }
@@ -33,7 +132,48 @@ public:
33132};
34133```
35134
36- ##C++代码层序遍历
135+ 当然回溯的地方可以精简，精简代码如下：
136+
137+ ```
138+ class Solution {
139+ public:
140+ int maxLen = INT_MIN;
141+ int maxleftValue;
142+ void traversal(TreeNode* root, int leftLen) {
143+ if (root->left == NULL && root->right == NULL) {
144+ if (leftLen > maxLen) {
145+ maxLen = leftLen;
146+ maxleftValue = root->val;
147+ }
148+ return;
149+ }
150+ if (root->left) {
151+ traversal(root->left, leftLen + 1); // 隐藏着回溯
152+ }
153+ if (root->right) {
154+ traversal(root->right, leftLen + 1); // 隐藏着回溯
155+ }
156+ return;
157+ }
158+ int findBottomLeftValue(TreeNode* root) {
159+ traversal(root, 0);
160+ return maxleftValue;
161+ }
162+ };
163+ ```
164+
165+ 如果对回溯部分精简的代码 不理解的话，可以看这篇[ 二叉树：找我的所有路径？] ( https://mp.weixin.qq.com/s/Osw4LQD2xVUnCJ-9jrYxJA ) 和[ 二叉树：以为使用了递归，其实还隐藏着回溯] ( https://mp.weixin.qq.com/s/ivLkHzWdhjQQD1rQWe6zWA ) 。这两篇文章详细分析了回溯隐藏在了哪里。
166+
167+
168+ ##迭代法
169+
170+ 本题使用层序遍历再合适不过了，比递归要好理解的多！
171+
172+ 只需要记录最后一行第一个节点的数值就可以了。
173+
174+ 如果对层序遍历不了解，看这篇[ 二叉树：层序遍历登场！] ( https://mp.weixin.qq.com/s/Gb3BjakIKGNpup2jYtTzog ) ，这篇里也给出了层序遍历的模板，稍作修改就一过刷了这道题了。
175+
176+ 代码如下：
37177
38178```
39179class Solution {
@@ -47,7 +187,7 @@ public:
47187 for (int i = 0; i < size; i++) {
48188 TreeNode* node = que.front();
49189 que.pop();
50- if (i == 0) result = node->val;
190+ if (i == 0) result = node->val; // 记录最后一行第一个元素
51191 if (node->left) que.push(node->left);
52192 if (node->right) que.push(node->right);
53193 }
@@ -56,3 +196,13 @@ public:
56196 }
57197};
58198```
199+
200+ #总结
201+
202+ 本题涉及如下几点：
203+
204+ * 递归求深度的写法，我们在[ 二叉树：我平衡么？] ( https://mp.weixin.qq.com/s/isUS-0HDYknmC0Rr4R8mww ) 中详细的分析了深度应该怎么求，高度应该怎么求。
205+ * 递归中其实隐藏了回溯，在[ 二叉树：以为使用了递归，其实还隐藏着回溯] ( https://mp.weixin.qq.com/s/ivLkHzWdhjQQD1rQWe6zWA ) 中讲解了究竟哪里使用了回溯，哪里隐藏了回溯。
206+ * 层次遍历，在[ 二叉树：层序遍历登场！] ( https://mp.weixin.qq.com/s/Gb3BjakIKGNpup2jYtTzog ) 深度讲解了二叉树层次遍历。
207+
208+ 所以本题涉及到的点，我们之前都讲解过，这些知识点需要同学们灵活运用，这样就举一反三了。