LeetCode513 Find Bottom Left Tree Value

文章目录
  1. 1. 描述
  2. 2. 样例
  3. 3. 思路
  4. 4. 代码

描述

Given a binary tree, find the leftmost value in the last row of the tree.

Note: You may assume the tree (i.e., the given root node) is not NULL.

样例

1
2
3
4
5
6
7
8
Input:

2
/ \
1 3

Output:
1
1
2
3
4
5
6
7
8
9
10
11
12
Input:

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

Output:
7

思路

输出二叉树最后一层最靠左的节点。

dfs一遍即可,具体看注释~

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
// pair第一维存深度,第二维存节点的值
pair<int, int> find(int dep, TreeNode* root) {
// 空节点随便返回一个不可能取到的小值
if (root == NULL) return make_pair(-1, -1);
// 叶节点返回当前深度以及节点的值
if (root->left == NULL && root->right == NULL) return make_pair(dep, root->val);
// 递归访问左右儿子节点
pair<int, int> l = find(dep + 1, root->left), r = find(dep + 1, root->right);
// 返回更深的结果,深度相同返回左儿子
return l.first >= r.first ? l : r;
}
int findBottomLeftValue(TreeNode* root) {
return find(1, root).second;
}
};
分享到 评论