513.Find Bottom Left Tree Value

一般而言似乎都用的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;
        
    }
};