题目地址(513. 找树左下角的值)

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

题目描述

  1. 给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
  3. 假设二叉树中至少有一个节点。
  7. 示例 1:
  9. 输入: root = [2,1,3]
  10. 输出: 1
  13. 示例 2:
  15. 输入: [1,2,3,4,null,5,6,null,null,7]
  16. 输出: 7
  21. 提示:
  23. 二叉树的节点个数的范围是 [1,104]
  24. -231 <= Node.val <= 231 - 1

前置知识


公司

  • 暂无

思路

使用bfs 层序遍历 将每层的第一个数作为最终返回值 直到最深层

关键点


代码

  • 语言支持：Java

Java Code:

  2. /**
  3.  * Definition for a binary tree node.
  4.  * public class TreeNode {
  5.  *     int val;
  6.  *     TreeNode left;
  7.  *     TreeNode right;
  8.  *     TreeNode() {}
  9.  *     TreeNode(int val) { this.val = val; }
  10.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  11.  *         this.val = val;
  12.  *         this.left = left;
  13.  *         this.right = right;
  14.  *     }
  15.  * }
  16.  */
  17. class Solution {
  18.         public int findBottomLeftValue(TreeNode root) {
  19.             Queue<TreeNode> queue = new LinkedList<>();
  20.             queue.offer(root);
  21.             int res = 0;
  22.             while (!queue.isEmpty()) {
  23.                 int size = queue.size();
  24.                 for (int i = 0; i < size; i++) {
  25.                     TreeNode poll = queue.poll();
  26.                     if (i == 0) {
  27.                         res = poll.val;
  28.                     }
  29.                     if (poll.left != null) {
  30.                         queue.offer(poll.left);
  31.                     }
  32.                     if (poll.right != null) {
  33.                         queue.offer(poll.right);
  34.                     }
  35.                 }
  36.             }
  37.             return res;
  38.         }
  39.     }

复杂度分析

令 n 为数组长度。

  • 时间复杂度：513. 找树左下角的值 - 图1#card=math&code=O%28n%29&id=igX5k)
  • 空间复杂度：513. 找树左下角的值 - 图2#card=math&code=O%28n%29&id=sy40Z)