LeetCode OJ 513. Find Bottom Left Tree Value

---

Description

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: 使用queue每次读取一层数据，先遍历左子树，然后遍历右子树。每一层的第一个数存到BottomLeft中，这样遍历到最后一层得到的结果就是BottomLeft的正确结果。每层的第一个数是每一层queue的队首元素front()。

代码

/** * 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) { if(!root->left && !root->right) return root->val; int BottomLeft, num; queue<TreeNode*> q; q.push(root); while(!q.empty()){ BottomLeft = q.front()->val; num = q.size(); while(num--){ TreeNode* node = q.front(); if(node->left) q.push(node->left); if(node->right) q.push(node->right); q.pop(); //num--; } } return BottomLeft; } };

方法二

BFS: 基于方法一的改进。每一层先遍历右子树，再遍历左子树。遍历到的最后一个数就是最后一层的第一个数。

代码

/** * 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) { if(!root->left && !root->right) return root->val; //Solution 2 int BottomLeft; queue<TreeNode*> q; q.push(root); while(!q.empty()){ TreeNode* node = q.front(); BottomLeft = node->val; q.pop(); if(node->right) q.push(node->right); if(node->left) q.push(node->left); } return BottomLeft; } };

方法三

DFS（Recursion）: 深度优先搜索。每次先递归遍历左子树，这时深度depth会发生变化，与全局变量d对比，d比depth小的时候，说明进入了新的一层，此时节点的值就是这一层的最左边的节点的值。所以递归深搜到最后一层的时候，返回的结果就是BottomLeft元素。

代码

个人github代码链接

/** * 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 { private: int BottomLeft = 0, d = 0; void DFS(const TreeNode* root, int depth){ if(!root) return ; if(d < depth){ d = depth; BottomLeft = root->val; } DFS(root->left, depth + 1); DFS(root->right, depth + 1); } public: int findBottomLeftValue(TreeNode* root) { if(!root->left && !root->right) return root->val; //Solution 3: Recursion DFS(root, 1); return BottomLeft; } };