( “树” 之 BFS) 513. 找树左下角的值 ——【Leetcode每日一题】

513. 找树左下角的值

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

示例 1:

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

示例 2:

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

提示:

• 二叉树的节点个数的范围是 [ 1 , 1 0 4 ] [1,10^4] [1,104]
• − 2 31 < = N o d e . v a l < = 2 31 − 1 -2^{31} <= Node.val <= 2^{31} - 1 −231<=Node.val<=231−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 最多保存 ⌈ n 2 ⌉ \\big \\lceil \\dfrac{n}{2} \\big \\rceil ⌈2n​⌉ 个节点。

题目来源：力扣。

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

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