014. 找树左下角的值_云泊683的博客-爱代码爱编程
题目链接:力扣
大概思路:
题目要求:
找到树的最底层里,最左边的节点的值。
递归法思路:
顺便一个遍历顺序,然后查找树最底层里,最左边的节点的值,然后返回。
树的最底层怎么判断?
到叶子节点就记录一个深度的最大值,同时记录这个叶子节点的值,然后继续遍历,遇见更大的深度,就改变收集的深度值和节点值,这样到遍历结束的时候,收集到的就是最底层的节点的值。
最左左节点"怎么收集的?(最底层的条件满足了)
递归顺序先向左,前中后序都是左右开始
遍历顺序为什么可以随意?
因为不需要在递归遍历过程中,对中节点做什么处理,只需要用到终止条件来更新数值。
递归三部曲:
1.确定递归函数的参数和返回值
参数输入树节点,返回树的最底层里,最左边的节点的值,返回int类型。
int findBottomLeftValue(TreeNode* root) {}
2.明确终止条件
遇见叶子节点的时候,更新深度最大值以及更新叶子节点的值,然后返回。
(第一次是记录,后面是判断要不要更新)
if (root->left == NULL && root->right == NULL) {
if (depth > maxDepth) {
maxDepth = depth; // 更新最大深度
result = root->val; // 最大深度最左面的数值
}
return;
}
3.确定单层递归逻辑
向左递归的下面加返回当前节点的值。然后结束返回。
(为防止空指针异常,要加个if判断指向下个节点的指针存不存在)
if (root->left) { // 左
depth++; // 深度加一
traversal(root->left, depth);
depth--; // 回溯,深度减一
}
if (root->right) { // 右
depth++; // 深度加一
traversal(root->right, depth);
depth--; // 回溯,深度减一
}
return;
4.总代码:
class Solution {
public:
int maxDepth = INT_MIN;//设计成最小方便更新
int result;
void traversal(TreeNode* root, int depth) {
if (root->left == NULL && root->right == NULL) {
if (depth > maxDepth) {
maxDepth = depth;
result = root->val;
}
return;
}
if (root->left) {
depth++;
traversal(root->left, depth);
depth--; // 回溯
}
if (root->right) {
depth++;
traversal(root->right, depth);
depth--; // 回溯
}
return;
}
int findBottomLeftValue(TreeNode* root) {
traversal(root, 0);
return result;
}
};
写代码时遇见的问题:
递归过程的深度数值变化过程没考虑进去。
个人想法:
感觉确实有些疑问在思路过程中没法解释的好。排版怎么排清晰点?