513.找树左下角的值

拼搏现实的明天。 2023-10-16 08:58 17阅读 0赞

### 513.找树左下角的值 ###

*  题干描述
 *  解题思路
 *   *  递归
     *   *  递归三部曲
         *   *  1. 确定递归函数的参数和返回值
             *  2. 确定终止条件
             *  3. 确定单层递归的逻辑
     *  迭代法
 *  具体代码
 *   *  递归法
     *  迭代法

# 题干描述 #

[513.找树左下角的值-力扣入口][513._-]

给定一个二叉树，在树的最后一行找到最左边的值。

示例1:  
![在这里插入图片描述][f09042b41b0749a0899cbb095b2236c5.png]  
示例2：  
![在这里插入图片描述][7ae95e48e1ef422986cec9a88f7cb482.png]

# 解题思路 #

本题要找出树的最后一行的最左边的值。此时大家应该想起用层序遍历是非常简单的了，反而用递归的话会比较难一点。

我们依然还是先介绍递归法。

## 递归 ##

其实就是找到最后一行，最左边的值。

最后一行通过找到深度最大的节点。

最左边的寻找可以使用前/中/后序，因为本题没有中间节点和处理逻辑，只要左优先就行。

### 递归三部曲 ###

#### 1. 确定递归函数的参数和返回值 ####

参数必须有要遍历的树的根节点，还有一个就是一个int型的变量用来记录最长深度。

这里就不需要返回值了，所以递归函数的返回值类型为void。

本题还需要类的两个全局变量，maxLen用来记录最大深度，result记录最大深度最左节点的数值。

代码如下：

int maxDepth = INT_MIN; // 全局变量 记录最大深度
    int result; // 全局变量 最大深度最左节点的数值
    void traversal(TreeNode* root, int depth)

#### 2. 确定终止条件 ####

当遇到叶子节点的时候，就需要统计一下最大的深度了，所以需要遇到叶子节点来更新最大深度。

代码如下：

if(root->left == NULL && root->right == NULL){
        
    	if(depth > maxDepth){
        
    		maxDepth = depth; // 更新最大深度
    		result = root->val; // 最大深度最左面的数值
    	}
    	return;
    }

#### 3. 确定单层递归的逻辑 ####

在找最大深度的时候，递归的过程中依然要使用回溯，代码如下：

// 中
    if(root->left){
             // 左
    	depth++; // 深度加一
    	traversal(root->left, depth);
    	depth--; // 回溯，深度减一
    }
    if(root->right){
            // 右
    	depth++; 
    	traversal(root->right, depth);
    	depth--; // 回溯，深度减一
    }
    return;

## 迭代法 ##

本题使用层序遍历再合适不过了，比递归要好理解得多。

只需要记录最后一行第一个节点的数值就可以了。

# 具体代码 #

## 递归法 ##

// 513.找树左下角的值 - 递归法
    private int Deep = -1;
    private int value = 0;
    public int findBottomLeftValue2(TreeNode root){
        
        value = root.val;
        findLeftValue(root, 0);
        return value;
    }
    
    private void findLeftValue(TreeNode root, int deep){
        
        if(root == null) return;
        if(root.left == null && root.right == null){
        
            if(deep > Deep){
        
                value = root.val;
                Deep = deep;
            }
        }
        if(root.left != null) findLeftValue(root.left, deep+1);
        if(root.right != null) findLeftValue(root.right, deep+1);
    }

## 迭代法 ##

// 513.找树左下角的值 - 迭代法
    public int findBottomLeftValue3(TreeNode root){
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int res = 0;
        while(!queue.isEmpty()){
        
            int size = queue.size();
            for(int i = 0;i < size; i++){
        
                TreeNode poll = queue.poll();
                if(i == 0){
        
                    res = poll.val;
                }
                if(poll.left != null){
        
                    queue.offer(poll.left);
                }
                if(poll.right != null){
        
                    queue.offer(poll.right);
                }
            }
        }
        return res;
    }

**参考资料**：[513.找树左下角的值][513.]

[513._-]: https://leetcode.cn/problems/find-bottom-left-tree-value/
[f09042b41b0749a0899cbb095b2236c5.png]: https://img-blog.csdnimg.cn/f09042b41b0749a0899cbb095b2236c5.png
[7ae95e48e1ef422986cec9a88f7cb482.png]: https://img-blog.csdnimg.cn/7ae95e48e1ef422986cec9a88f7cb482.png
[513.]: https://programmercarl.com/0513.%E6%89%BE%E6%A0%91%E5%B7%A6%E4%B8%8B%E8%A7%92%E7%9A%84%E5%80%BC.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE