题意:获取tree最左边的一个元素
ref{:target=”_blank”}
C++ 代码
dfs,传递一个当前搜索的深度,当深度大于最深的时候,update答案;
先搜索left,再搜索right
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int findBottomLeftValue(TreeNode* root) {
dfs(root, 0);
return res;
}
void dfs(TreeNode* root, int depth) {
if(!root)return;
// 更新答案的条件
if(depth > max_depth_) {
max_depth_ = depth;
res = root->val;
}
dfs(root->left, depth+1);
dfs(root->right, depth+1);
}
private:
int max_depth_ = -1;
int res = 0;
};
// BFS
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int findBottomLeftValue(TreeNode* root) {
queue<TreeNode*> q;
q.push(root);
vector<vector<int>> nodes;
while(q.size()) {
vector<int> level;
int sz = q.size();
while(sz--) {
auto t = q.front();
level.push_back(t->val);
if(t->left)q.push(t->left);
if(t->right)q.push(t->right);
nodes.push_back(level);
q.pop();
}
}
return nodes.back().front();
}
};
BFS 不用存储各个level的值,直接迭代即可
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int findBottomLeftValue(TreeNode* root) {
queue<TreeNode*> q;
q.push(root);
int res = 0;
while(q.size()) {
int sz = q.size();
// update answer
res = q.front()->val;
while(sz--) {
auto t = q.front();
if(t->left)q.push(t->left);
if(t->right)q.push(t->right);
q.pop();
}
}
return res;
}
};