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.
其实本题目的意思是找二叉树最底层的第一个叶子节点
思路1:用队列实现
int findBottomLeftValue(TreeNode* root) {
if (root == NULL)return 0;
queue<TreeNode *> temp;
int val = 0;
temp.push(root);
while (!temp.empty()){
int size = temp.size();
val = temp.front()->val;
while (size--){
TreeNode *p = temp.front();
temp.pop();
if (p->left)temp.push(p->left);
if (p->right)temp.push(p->right);
}
}
return val;
}
思路2:递归
class Solution {
private:
int height = 0, val = 0;
public:
void helper(TreeNode *root, int depth){
if (root == NULL)return;
if (height < depth){
val = root->val;
height = depth;
}
helper(root->left, depth + 1);
helper(root->right, depth + 1);
}
int findBottomLeftValue(TreeNode* root) {
if (root == NULL)return 0;
helper(root, 1);
return val;
}
};