513. 找树左下角的值

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

示例 1:

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

示例 2:

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

提示:

• 二叉树的节点个数的范围是 $[1,10^4]$
• $-2^{31}<=Node.val<=2^{31}-1$

思路：BFS

队列先存放root的右节点，再存放左节点，这样遍历到最后，队列中最后一个元素即为该树左下角的值。

代码：(Java、C++)

Java

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public int findBottomLeftValue(TreeNode root) {Queue<TreeNode> que = new LinkedList<>();que.add(root);while(!que.isEmpty()){root = que.poll();if(root.right != null) que.add(root.right);if(root.left != null) que.add(root.left);}return root.val;}
}

C++

/*** 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) {queue<TreeNode*> que;que.push(root);while(!que.empty()){root = que.front();if(root->right != NULL) que.push(root->right);if(root->left != NULL) que.push(root->left);que.pop();}return root->val;}
};

运行结果：

复杂度分析：

• 时间复杂度：$O(n)$，其中 n 是二叉树的节点数目。
• 空间复杂度：$O(n)$，如果二叉树是满完全二叉树，那么队列 que 最多保存 $\lceil \frac{n}{2}\rceil$ 个节点。

题目来源：力扣。

放弃一件事很容易，每天能坚持一件事一定很酷，一起每日一题吧！
关注我 leetCode专栏，每日更新！

注： 如有不足，欢迎指正！