美文网首页Leedcode
515. Find Largest Value in Each

515. Find Largest Value in Each

作者: 凉拌姨妈好吃 | 来源:发表于2018-05-25 19:53 被阅读0次

    题目:查找每层的最大值,保存到vector中

    先说一下一开始我的bug,我一开始的思路是把vector都初始化为0,然后再一个个替换掉,那么这就会出现超时问题!!后面修改了一下,不初始化vector,而是将容器大小与当前节点层数比较,如果小于当前节点层数,就插入当前节点的值。

    /**
     * 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:
        vector<int> largestValues(TreeNode* root) {
            vector<int> value;
            if(!root)
                return value;
            findLevelLargestValue(root,0,value);
            return value;
        }
        
        void findLevelLargestValue(TreeNode * root,int depth,vector<int>& value){
            if(!root)
                return;
            
            if(depth>=value.size())
            {
                value.push_back(root->val);
            }
            else
            {
                if(root->val>value[depth])
                {
                    value[depth]=root->val;
                }
            }
                
            findLevelLargestValue(root->left,depth+1,value);
            findLevelLargestValue(root->right,depth+1,value);
            
        }
    };
    

    下面是leedcode上大神的解法,空间复杂度为O(1),采用的是Morris Traversal

    class Solution {
    public:
        vector<int> largestValues(TreeNode* root) {
            vector<int> res;
            TreeNode* cur = root, *prev = NULL;
            int deep = 0;
            while (cur) {
                if (cur->left == NULL) {
                    //
                    if (deep >= res.size())
                        res.push_back(cur->val);
                    else
                        res[deep] = max(res[deep], cur->val);
                    cur = cur->right;
                    deep++;
                } else {
                    prev = cur->left;
                    int move = 1;
                    while (prev->right && prev->right != cur) {
                        prev = prev->right;
                        move++;
                    }
                    if (prev->right == NULL) {
                        if (deep >= res.size())
                            res.push_back(cur->val);
                        prev->right = cur;
                        cur = cur->left;
                        deep++;
                    } else {
                        // back to parent node, remove connection
                        prev->right = NULL;
                        deep -= move + 1;
                        //
                        if (deep >= res.size())
                            res.push_back(cur->val);
                        else
                            res[deep] = max(res[deep], cur->val);
                        cur = cur->right;
                        deep++;
                    }
                }
            }
            return res;
        }
    };
    

    相关文章

      网友评论

        本文标题:515. Find Largest Value in Each

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