513. Find Bottom Left Tree Value

题目描述：

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:

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

解题思路：

遍历整棵树，记录每个节点的值和深度，得到最大深度值，第一个深度值等于最大深度值的节点为所要求的节点。

代码：

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     int findBottomLeftValue(TreeNode* root) {
13         bfs(root, 0);
14         int max_height = -1;
15         for (auto h : height) {
16             if (h > max_height)
17                 max_height = h;
18         }
19         int i = 0;
20         for (; i < height.size(); ++i) {
21             if (height[i] == max_height) {
22                 break;
23             }
24         }
25         return node[i];
26     }
27     vector<int> node;
28     vector<int> height;
29     void bfs(TreeNode* root, int h) {
30         if (root == NULL) 
31             return;
32         if (root->left != NULL)
33             bfs(root->left, h+1);
34         if (root->right != NULL) 
35             bfs(root->right, h+1);
36         node.push_back(root->val);
37         height.push_back(h);
38     }
39 };