leetcode 513. Find Bottom Left Tree Value

淩亂°似流年 2022-06-13 00:16 227阅读 0赞

1.题目

Given a binary tree, find the leftmost value in the last row of the tree.
给定一棵二叉树，返回最底层的最左边叶子节点的值。
Example 1:
Input:

  1. 2
  2.    / \
  3.   1   3

Output:
1

Example 2:
Input:

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

Output:
7
假设根结点不为空。

2.分析

BFS：按层来遍历节点，返回最底层左边第一个节点的值。

如果是从左往右遍历，需要用一个变量来记录当前层的高度。
如果是从右往左遍历，直接返回遍历的最后一个节点的值即可。这种方法是比较好的。

3.代码

BFS，从右往左遍历。直接返回最后一个遍历的节点的值。
最后一个遍历的节点一定是最底层的最左边的节点。

  1. class Solution {
  2. public:
  3.     int findBottomLeftValue(TreeNode* root) {
  4.         queue<TreeNode*> nodes;
  5.         nodes.push(root);
  6.         while (!nodes.empty()) {
  7.             root = nodes.front();
  8.             nodes.pop();
  9.             if (root->right)
  10.                 nodes.push(root->right);
  11.             if (root->left)
  12.                 nodes.push(root->left);
  13.         }
  14.         return root->val;
  15.     }
  16. };

发表评论

表情：
评论列表 （有 0 条评论，227人围观）

还没有评论，来说两句吧...

相关阅读