# 513. Find Bottom Left Tree Value 找树左下角的值

@TOC

## # 题目描述

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

Example 1:

``````Input:

2
/ \
1   3

Output:
1
``````

Example 2:

``````Input:

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

Output:
7
``````

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

## # 解题方法

### # BFS

``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int findBottomLeftValue(TreeNode root) {
int ans = 0;
tree.offer(root);
while(!tree.isEmpty()){
TreeNode temp = tree.poll();
if(temp.right != null){
tree.offer(temp.right);
}
if(temp.left != null){
tree.offer(temp.left);
}
ans = temp.val;
}
return ans;
}
}
``````

Python做法是用层次遍历，用的是双向队列，所以注意append和popleft。代码如下：

``````# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def findBottomLeftValue(self, root):
"""
:type root: TreeNode
:rtype: int
"""
q = collections.deque()
q.append(root)
res = []
while q:ruxai
size = len(q)
level = []
for i in range(size):
node = q.popleft()
if not node: continue
level.append(node.val)
q.append(node.left)
q.append(node.right)
if level:
res.append(level)
return res[-1][0]
``````

``````/**
* 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:
int findBottomLeftValue(TreeNode* root) {
queue<TreeNode*> q;
q.push(root);
vector<vector<int>> res;
while (!q.empty()) {
int size = q.size();
vector<int> level;
for (int i = 0; i < size; i++) {
TreeNode* node = q.front(); q.pop();
if (!node) continue;
level.push_back(node->val);
q.push(node->left);
q.push(node->right);
}
if (!level.empty()) {
res.push_back(level);
}
}
return res[res.size() - 1][0];
}
};
``````

### # DFS

python代码如下：

``````# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def findBottomLeftValue(self, root):
"""
:type root: TreeNode
:rtype: int
"""
res = []
self.dfs(root, res, 0)
return res[-1][0]

def dfs(self, root, res, level):
if not root: return
if level == len(res): res.append([])
res[level].append(root.val)
self.dfs(root.left, res, level + 1)
self.dfs(root.right, res, level + 1)
``````

C++代码需要注意的是，我们应该对res传引用进来，否则不能对外部变量进行更改。

``````/**
* 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:
int findBottomLeftValue(TreeNode* root) {
dfs(root, res, 0);
return res[res.size() - 1][0];
}
private:
vector<vector<int>> res;
void dfs(TreeNode* root, vector<vector<int>>& res, int level) {
if (!root) return;
if (level == res.size()) res.push_back({});
res[level].push_back(root->val);
dfs(root->left, res, level + 1);
dfs(root->right, res, level + 1);
}
};
``````

2017 年 4 月 13 日