一般而言似乎都用的BFS,自己用的是递归,建立了一个新结构,不是特别好看,效率还行。
自己的代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
struct Output{
int depth;
int num;
};
class Solution {
public:
Output findValue(TreeNode* root) {
Output i = {0,0};
if (root == NULL)
return i;
if (root->left==NULL && root->right == NULL){
i.depth = 1;
i.num = root->val;
return i;
}
Output l = findValue(root->left);
Output r = findValue(root->right);
if (l.depth >= r.depth){
i.depth = l.depth + 1;
i.num = l.num;
}else{
i.depth = r.depth + 1;
i.num = r.num;
}
return i;
}
int findBottomLeftValue(TreeNode* root) {
return findValue(root).num;
}
};
BFS代码
class Solution {
public:
int findLeftMostNode(TreeNode* root) {
queue<TreeNode*> q;
queue<int> level;
q.push(root);
level.push(0);
int m=0;
while(q.size()){
TreeNode *r = q.front(); q.pop();
int l = level.front(); level.pop();
if(r->left) {
q.push(r->left);
level.push(l+1);
}
if(r->right){
q.push(r->right);
level.push(l+1);
}
if(l > m){
m = l;
root = r;
}
}
return root->val;
}
};
网友评论