找树左下角的值

描述

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

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

示例 1:

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

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

提示:

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

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

题解

C++代码

这道题用层序遍历更直接一些，因为层序遍历时遍历完当前行所有结点之后才去下一行，那么我们再遍历每行第一个结点时更新结果res即可，根本不用维护最大深度。

/**
 * 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 res = 0; // 保存结果
        queue<TreeNode*> q; // 定义队列进行层序遍历
        q.push(root); // 根节点入队
        while(!q.empty()){
            int n = q.size();
            // 遍历每一层的节点
            for(int i =0; i<n; i++){
                TreeNode* t = q.front();
                q.pop();
                if(i == 0) res = t->val;
                if(t->left) q.push(t->left);
                if(t->right) q.push(t->right);
            }
        }
        return res;
    }
};

我们还可以使用个小trick，使得其更加的简洁，由于一般的层序是从左往右的，那么如果我们反过来，每次从右往左遍历，这样就不用检测每一层的起始位置了，最后一个处理的结点一定是最后一层的最左结点，我们直接返回其结点值即可。

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            root = q.front(); q.pop();
            if (root->right) q.push(root->right);
            if (root->left) q.push(root->left);
        }
        return root->val;
    }
};

Python代码

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        q = [root] # 定义一个队列
        while q:
            t = q.pop(0)
            if t.right:
                q.append(t.right)
            if t.left:
                q.append(t.left)
        return t.val