美文网首页
513.Find Bottom Left Tree Value

513.Find Bottom Left Tree Value

作者: 殷水臣 | 来源:发表于2017-02-20 20:01 被阅读0次

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

    相关文章

      网友评论

          本文标题:513.Find Bottom Left Tree Value

          本文链接:https://www.haomeiwen.com/subject/vkwewttx.html