題目描述:
給定一個二叉樹,在樹的最後一行找到最左邊的值。
示例 1:
輸入:
2
/ \
1 3
輸出:
1
示例 2:
輸入:
1
/ \
2 3
/ / \
4 5 6
/
7
輸出:
7
注意: 您可以假設樹(即給定的根節點)不為 NULL。
思路1:此題目第一眼看到就想起了二叉樹的右視圖。這個題跟此題類似,可以按照二叉樹的左視圖來做,最後隻需要傳回最後一層的值即可
/**
* 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) {
vector<int> res;
queue<TreeNode*> que;
que.push(root);
while(!que.empty()){
int size=que.size();
res.push_back(que.front()->val);
while(size--){
TreeNode* now=que.front();
que.pop();
if(now->left)
que.push(now->left);
if(now->right)
que.push(now->right);
}
}
return res[res.size()-1];
}
};
/**
* 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 res=-1,maxdepth=-1;
void inorder(TreeNode* root,int depth){
if(root==NULL)
return ;
inorder(root->left,depth+1);
if(maxdepth<depth){
maxdepth=depth;
res=root->val;
}
inorder(root->right,depth+1);
}
int findBottomLeftValue(TreeNode* root) {
inorder(root,0);
return res;
}
};