2019-03-17 right view of binary

拿到题目就觉得，挺简单的，于是写下代码：

/**

* 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> rightSideView(TreeNode* root) {

        map<int, int> viewOfLevel;

        int depth = travel(root, 0, viewOfLevel);

        vector<int> view(depth + 1);

        for (int i = 0; i <= depth; i++) {

            view.push_back(viewOfLevel[i]);

        }

        return view;

    }

    int travel(TreeNode *node, int curDepth, map<int, int> &viewOfLevel) {

        if (node != NULL) {

            viewOfLevel[curDepth] = node->val; 

            int leftDepth = travel(node->left, curDepth + 1, viewOfLevel);

            int rightDepth = travel(node->right, curDepth + 1, viewOfLevel);

            return max(leftDepth, rightDepth);

        } else {

            return curDepth - 1;

        }

    }

};

测试用例是[1,2,3,null,5,null,4]，答案是[1,3,4]，程序却输出了[0,0,0,1,3,4]，奇怪了，

后来在playground上面，加了些日志，发现计算过程中depth和val都是正确的，就是输出多了3个零。定睛一看，会不是是vector<int> view(depth + 1);这里的问题？本来是想着初始化的时候直接一次性把内存分配好，以后就不用扩容了……难道这里会直接把3个0加进去？

把它改成vector<int> view，果然就好了……api不熟的情况下用起来还真是有坑……

如果想提前分配内存，应该把 view.push_back(viewOfLevel[i]);改成view[i] = viewOfLevel[i];

提前分配内存的算法，成绩是：

Runtime:4 ms, faster than 100.00% of C++ online submissions forBinary Tree Right Side View.

Memory Usage:10 MB, less than 8.00% of C++ online submissions forBinary Tree Right Side View.