# 513.找树左下角的值

<https://leetcode-cn.com/problems/find-bottom-left-tree-value/>

* [513.找树左下角的值](https://suki.gitbook.io/91-days-algorithm/basic/binary-tree/pages/-MNWDomhauKB8raP29In#513找树左下角的值)
  * [题目描述](https://suki.gitbook.io/91-days-algorithm/basic/binary-tree/pages/-MNWDomhauKB8raP29In#题目描述)
  * [方法 1：层次遍历](https://suki.gitbook.io/91-days-algorithm/basic/binary-tree/pages/-MNWDomhauKB8raP29In#方法-1层次遍历)
    * [思路](https://suki.gitbook.io/91-days-algorithm/basic/binary-tree/pages/-MNWDomhauKB8raP29In#思路)
    * [伪代码](https://suki.gitbook.io/91-days-algorithm/basic/binary-tree/pages/-MNWDomhauKB8raP29In#伪代码)
    * [代码(JavaScript/Python/C++)](https://suki.gitbook.io/91-days-algorithm/basic/binary-tree/pages/-MNWDomhauKB8raP29In#代码javascriptpythonc)
    * [复杂度分析](https://suki.gitbook.io/91-days-algorithm/basic/binary-tree/pages/-MNWDomhauKB8raP29In#复杂度分析)
  * [方法 2：DFS](https://suki.gitbook.io/91-days-algorithm/basic/binary-tree/pages/-MNWDomhauKB8raP29In#方法-2dfs)
    * [思路](https://suki.gitbook.io/91-days-algorithm/basic/binary-tree/pages/-MNWDomhauKB8raP29In#思路-1)
    * [伪代码](https://suki.gitbook.io/91-days-algorithm/basic/binary-tree/pages/-MNWDomhauKB8raP29In#伪代码-1)
    * [复杂度分析](https://suki.gitbook.io/91-days-algorithm/basic/binary-tree/pages/-MNWDomhauKB8raP29In#复杂度分析-1)
    * [代码(JavaScript/Python/C++)](https://suki.gitbook.io/91-days-algorithm/basic/binary-tree/pages/-MNWDomhauKB8raP29In#代码javascriptpythonc-1)

## 题目描述

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

示例 1:

输入:

    2
   / \
  1   3

输出:
1


示例 2:

输入:

        1
       / \
      2   3
     /   / \
    4   5   6
       /
      7

输出:
7


注意: 您可以假设树（即给定的根节点）不为 NULL。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-bottom-left-tree-value
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
```

## 方法 1：层次遍历

### 思路

按照题目意思我们只需要找到最后一层，返回最左边的节点即可。

所以只要对二叉树进行层次遍历，等遍历到最后一层的时候，返回第一个节点。

![bfs](https://cdn.jsdelivr.net/gh/suukii/91-days-algorithm/assets/513_0.png)

### 伪代码

层次遍历模板 1：

```
新建 curLevel 数组保存当前层的节点；
新建 nextLevel 数组保存下一层要遍历的节点；

将 root 加入到 curLevel 中，开始遍历；

重复以下操作：
    遍历 curLevel 中的节点：
        如果该节点存在左子节点，把左子节点加入到 nextLevel 中；
        如果该节点存在右子节点，把右子节点加入到 nextLevel 中；

    判断 nextLevel 中是否有节点：
        如果没有，说明已经遍历到树的最深层次，此时 curLevel 中放的是最深层的所有叶子节点，返回第一个即可；

    让 nextLevel 作为下一个循环中要遍历的对象，即 curLevel = nextLevel；
    将 nextLevel 清空；
```

层次遍历模板 2：

```javascript
const queue = [root];

while (queue.length) {
    // 先记录这一层的节点数
    let len = queue.length;

    while (len--) {
        const node = queue.shift();
        node.left && queue.push(node.left);
        node.right && queue.push(node.right);
    }
}
```

### 代码(JavaScript/Python/C++)

JavaScript Code

```javascript
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var findBottomLeftValue = function (root) {
    let curLevel = [root],
        nextLevel = [];

    while (true) {
        for (let node of curLevel) {
            node.left && nextLevel.push(node.left);
            node.right && nextLevel.push(node.right);
        }

        if (!nextLevel.length) return curLevel[0].val;

        curLevel = nextLevel;
        nextLevel = [];
    }
};
```

Python Code

```python
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def findBottomLeftValue(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        curLevel, nextLevel = [root], []
        while True:
            for node in curLevel:
                if node.left: nextLevel.append(node.left)
                if node.right: nextLevel.append(node.right)
            if not nextLevel: return curLevel[0].val
            curLevel, nextLevel = nextLevel, []
```

JavaScript Code

```javascript
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var findBottomLeftValue = function (root) {
    if (!root) return 0;

    const queue = [root];
    let bottomLeft = null;
    while (queue.length) {
        let len = queue.length;

        // 每遍历一层就更新一次最左节点
        // 最后一层更新就是最后一层的的最左节点
        bottomLeft = queue[0];

        while (len--) {
            const node = queue.shift();
            node.left && queue.push(node.left);
            node.right && queue.push(node.right);
        }
    }
    return bottomLeft.val;
};
```

C++ Code

```cpp
/**
 * 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) {
        TreeNode* bottom_left = nullptr;
        queue<TreeNode*> level;
        level.push(root);

        while (!level.empty()) {
            int size = level.size();
            bottom_left = level.front();

            while (size--) {
                TreeNode* node = level.front();
                level.pop();
                if (node->left) level.push(node->left);
                if (node->right) level.push(node->right);
            }
        }

        return bottom_left->val;

    }
};
```

### 复杂度分析

* 时间复杂度：$O(N)$，其中 N 为节点数。
* 空间复杂度: $O(q)$，q 为队列长度。最坏情况是满二叉树，此时 q 为 $2/N$，即为 $O(N)$，N 为二叉树节点数。

## 方法 2：DFS

### 思路

想一下递归的路线，如果我们先递归遍历左子树再遍历右子树，那么每遍历到新一层的时候，都是先访问最左边的节点。

![](https://cdn.jsdelivr.net/gh/suukii/91-days-algorithm/assets/513_1.png)

* 所以我们只需要在遍历到新一层的时候，记录第一个节点。
* 用 `depth` 来记录当前层次，用 `maxDepth` 来记录已经遍历过的最深层次，当 `depth > maxDepth` 的时候，说明遍历到了新层次：
  * 记录第一个节点的值
  * 更新 `maxDepth`

### 伪代码

```
创建 ans 来记录遍历中遇到的最左边的子节点
创建 maxDepth 来记录已经遍历到的最深层次

定义一个 dfs 函数来遍历二叉树，函数接收 (node, depth) 两个参数，node 是当前遍历到的节点，depth 是当前遍历深度：
    如果 node 为 null，终止遍历

    // 因为我们是先遍历左子节点，再遍历右子节点
    // 所以第一次 depth > maxDepth 的时候，遍历到的就是 depth 这一层最左边的子节点
    // 接着我们更新 maxDepth，之后遍历同一 depth 的节点时，ans 都不会更新了
    如果当前层级 depth > maxDepth：
        更新 ans 为 node.val
        更新 maxDepth 为 depth

    // 分别递归遍历左右子树
    dfs(node.left, depth + 1)
    dfs(node.right, depth + 1)

调用 dfs 函数，传入 (root, 0)
返回 ans
```

### 复杂度分析

* 时间复杂度：$O(N)$，其中 N 为节点数。
* 空间复杂度：$O(h)$，其中 $h$ 为树的深度，最坏的情况 $h$ 等于 $N$，其中 N 为节点数，此时树退化到链表。

### 代码(JavaScript/Python/C++)

JavaScript Code

```javascript
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var findBottomLeftValue = function (root) {
    let maxDepth = 0;
    let ans = 0;
    helper(root, 1);
    return ans;

    // ******************************

    function helper(root, depth) {
        if (!root) return 0;

        if (depth > maxDepth) {
            maxDepth = depth;
            ans = root.val;
        }

        helper(root.left, depth + 1);
        helper(root.right, depth + 1);
    }
};
```

Python Code

```python
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    _ans = 0
    _maxDepth = 0

    def helper(self, root, depth):
        if root is None: return 0

        if depth > self._maxDepth:
            self._maxDepth = depth
            self._ans = root.val

        self.helper(root.left, depth + 1)
        self.helper(root.right, depth + 1)

    def findBottomLeftValue(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.helper(root, 1)
        return self._ans
```

C++ Code

```cpp
/**
 * 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) {
        findBottomLeftValue(root, 1);
        return ans_;
    }
    void findBottomLeftValue(TreeNode* root, int depth) {
        if (depth > max_depth_) {
            max_depth_ = depth;
            ans_ = root->val;
        }

        if (root->left) findBottomLeftValue(root->left, depth + 1);
        if (root->right) findBottomLeftValue(root->right, depth + 1);
    }
private:
    int max_depth_ = 0;
    int ans_;
};
```

更多题解可以访问：<https://github.com/suukii/91-days-algorithm>


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://suki.gitbook.io/91-days-algorithm/basic/binary-tree/16.find-bottom-left-tree-value.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.