題目：查找每層的最大值留美，保存到vector中

先說(shuō)一下一開(kāi)始我的bug涧黄，我一開(kāi)始的思路是把vector都初始化為0拙寡，然后再一個(gè)個(gè)替換掉鸵鸥，那么這就會(huì)出現(xiàn)超時(shí)問(wèn)題Ｍ沂臁垮抗！后面修改了一下盟庞，不初始化vector捞稿，而是將容器大小與當(dāng)前節(jié)點(diǎn)層數(shù)比較鳄厌，如果小于當(dāng)前節(jié)點(diǎn)層數(shù)荞胡，就插入當(dāng)前節(jié)點(diǎn)的值。

/**
 * 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上大神的解法了嚎，空間復(fù)雜度為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;
    }
};