算法力扣刷题记录 四十八【513.找树左下角的值】

前言

二叉树篇继续。
记录 四十八【513.找树左下角的值】

---

一、题目阅读

给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。

假设二叉树中至少有一个节点。

示例 1:

输入: root = [2,1,3]
输出: 1
1
2

示例 2:

输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7
1
2

提示:

二叉树的节点个数的范围是 [1,104]
-2^31 <= Node.val <= 2^31 - 1 
1
2

---

二、尝试实现

找最底层最左边的节点，依然要遍历树。
（1）确定遍历顺序：前序。因为需要获得最大深度，从上到下获取深度，使用前序遍历（中左右）。
（2）使用递归实现：那么按步骤确定。

• 确定参数：需要传入节点——TreeNode* cur；需要传入深度——int depth，不是引用，为了方便回溯使用副本；需要记录结果——int& result，这是引用，方便替换值，所以不使用副本。
• 确定返回值：结果在参数result中有记录，所以不需要返回值了。
• 确定终止条件：当遇到叶子节点可以return。遇到叶子节点还有处理逻辑：
  • 判断这个叶子节点的深度是不是记录的最大深度。如果是，更新当前遍历的最大深度，同时更新result。因为中左右的顺序，如果是更深的一层，肯定是最左边的叶子。
• 确定逻辑：
  • 中：不用处理什么；
  • 左：如果cur->left存在，深入遍历，传递depth+1；
  • 右：如果cur->right存在，深入遍历，传递depth+1；和左的逻辑一样。

代码实现【递归】

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxdepth = 1;//记录当前遍历的最大深度
    void traversal(TreeNode* cur,int depth,int& result){
        if(!cur->left && !cur->right){//叶子节点
            if(depth > maxdepth){
                maxdepth = depth;
                result = cur->val;
            }
            return;
        }
        if(cur->left){
            traversal(cur->left,depth+1,result);
        }
        if(cur->right){
            traversal(cur->right,depth+1,result);
        }
    }
    int findBottomLeftValue(TreeNode* root) {
        int result;
        traversal(root,1,result);
        return result;
    }
};
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

---

三、参考学习

参考学历链接

学习内容

1. 概念确定：左下角的值——最后一层最左边的值。
2. 递归思路：深度最大就是最后一行；最左边：涉及遍历顺序。前中后都可以。

• 遍历顺序原因：因为中没有处理逻辑，所以只要左在右的前面就好；前序（中左右）、中序（左中右）、后序（左右中）都是左在右的前面。
• 注意：depth要回溯。

3. 递归代码实现：就是二、中的代码实现。

4. 迭代思路：遍历到一层，先把这一层第一个节点记录下来；后面还有新的层，就替换新一层的第一个节点；那么记录的结果就是最后一层的第一个节点。

5. 迭代代码实现：

   /**
    * Definition for a binary tree node.
    * struct TreeNode {
    *     int val;
    *     TreeNode *left;
    *     TreeNode *right;
    *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
    *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
    * };
    */
   class Solution {
   public:
       int findBottomLeftValue(TreeNode* root) {
           int result;
           queue<TreeNode*> q;
           q.push(root);
           while(!q.empty()){
               int size = q.size();
               for(int i = 0;i < size;i++){
                   TreeNode* cur = q.front();
                   q.pop();
                   if(i == 0){
                       result = cur->val;
                   }
                   if(cur->left) q.push(cur->left);
                   if(cur->right) q.push(cur->right);
               }
           }
           return result;
       }
   };
   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

---

总结

【513.找树左下角的值】

链接： 三十七【二叉树层序遍历】 和四十三【最大、最小深度问题】

（欢迎指正，转载标明出处）