题目描述

这个题让你按照从左到右，从上到下的顺序print 树的值，从上到下的话BFS可以搞定，从左到右的话需要一个纪录位置的坐标，存下来。

Map的insert，delete，search的复杂度都是O（log m），where m 是map的key数，这里假设有n的node，我认为复杂度是（n log（log（n)) 很接近于 n 了。为啥要用map 而不是unordered_map呢，因为要保留顺序呀

样例

class Solution {
public:
    vector<vector<int>> verticalOrder(TreeNode* root) {

        vector<vector<int>> output;

        if (root == NULL){
            return output;
        }

        map<int, vector<int>> Map;

        queue<pair<int, TreeNode*>> Q;

        Q.push(make_pair(0, root));

        while(!Q.empty()){
            int size = Q.size();

            for (int i = 0; i < size; i++){
                int location = Q.front().first;
                TreeNode* node = Q.front().second;

                Q.pop();

                Map[location].push_back(node->val);

                if (node->left != NULL){
                    Q.push(make_pair(location - 1, node->left));
                }

                if (node->right != NULL){
                    Q.push(make_pair(location + 1, node->right));
                }

            }            
        }

        for (auto & element : Map){
            output.push_back(element.second);
        }

        return output;  
    }
};

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度分析：blablabla

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度分析：blablabla

C++ 代码

blablabla