Leetcode 987: обход двоичного дерева в вертикальном порядке: почему я получаю TLE?

Question

Я нахожу вертикальный обход BFS. Для каждого узла я рассчитал его горизонтальное расстояние. Узлы с одинаковым hd будут встречаться вместе при вертикальном обходе. Для root hd будет 0. Если мы go левый HD = HD-1, для правого HD = HD + 1

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> verticalTraversal(TreeNode* root) {
        vector<vector<int>> result;
        
        if(root==NULL)
            return result;
        
        queue<pair<TreeNode*,int>> myqueue;
        
        unordered_map<int,vector<int>> my_map;
        int hd=0;
        myqueue.push(make_pair(root,hd));
        
        while(!myqueue.empty())
        {
            pair <TreeNode*,int> mypair = myqueue.front();
            myqueue.pop();
            hd = mypair.second;
            TreeNode* temp = mypair.first;
            my_map[hd].push_back(temp->val);
         //   myqueue.pop();
            if(temp->left!=nullptr)
                myqueue.push(make_pair(root->left,hd-1));
            if(temp->right!=nullptr)
                myqueue.push(make_pair(root->right,hd+1));
            
        }
        
        //vector<temp>;
        unordered_map<int,vector<int>> :: iterator it;
        
        for(it=my_map.begin();it!=my_map.end();it++)
        {
            vector<int> temp;
            for(int i=0;i<it->second.size();i++)
            {
                temp.push_back(it->second[i]);
            }
            result.push_back(temp);
        }
        
        
        
        return result;
    }
        
};

Answer 1

Вероятно, myqueue никогда не опорожняется.

Вот похожий BFS, который прошел бы:

// This block might trivially optimize the exec time;
// Can be removed;

static const auto __optimize__ = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    return 0;
}();


// Most of headers are already included;
// Can be also removed;

#include <cstdint>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#include <map>


// Solution
static const struct Solution {
    static const struct Node {
        const TreeNode* node;
        const int x;
        const int y;
    };

    static const std::vector<std::vector<int>> verticalTraversal(
                                   const TreeNode* root
    ) {
        std::vector<std::vector<int>> vertical_nodes;
        std::map<int, std::map<int, std::vector<int>>> mapvect;
        std::queue<Node*> nodes_q;
        nodes_q.push(new Node{root, 0, 0});

        while (!nodes_q.empty()) {
            auto curr = nodes_q.front();
            nodes_q.pop();

            if (curr->node->left) {
                nodes_q.push(new Node{curr->node->left, curr->x - 1, curr->y + 1});
            }

            if (curr->node->right) {
                nodes_q.push(new Node{curr->node->right, curr->x + 1, curr->y + 1});
            }

            mapvect[curr->x][curr->y].emplace_back(curr->node->val);
        }

        for (std::pair<int, std::map<int, std::vector<int>>> i : mapvect) {
            vertical_nodes.push_back({});
            for (std::pair<int, std::vector<int>> j : i.second) {
                std::vector<int> vals = j.second;
                std::sort(std::begin(vals), std::end(vals));
                vertical_nodes.back().insert(
                    std::end(vertical_nodes.back()),
                    std::begin(vals),
                    std::end(vals)
                );
            }
        }

        return vertical_nodes;
    }
};

Вот DFS, возможно, проще в реализации:

// This block might trivially optimize the exec time;
// Can be removed;

const static auto __optimize__ = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    return 0;
}();

#include <cstdint>
#include <vector>
#include <map>
#include <set>

const static struct Solution {
    static std::vector<std::vector<int>> verticalTraversal(
                                          const TreeNode* root
    ) {
        std::vector<std::vector<int>> vertical_nodes;
        std::map<int, std::map<int, std::set<int>>> mapset;
        depthFirstSearch(root, 0, 0, mapset);
        for (auto x = std::begin(mapset); x != std::end(mapset); ++x) {
            vertical_nodes.emplace_back(std::vector<int>());
            for (auto y = std::begin(x->second); y != std::end(x->second); ++y) {
                vertical_nodes.back().insert(
                    std::end(vertical_nodes.back()),
                    std::begin(y->second),
                    std::end(y->second)
                );
            }
        }

        return vertical_nodes;
    }

    static const void depthFirstSearch(
        const TreeNode* node,
        const int x,
        const int y,
        std::map<int, std::map<int, std::set<int>>>& mapset
    ) {
        if (node != NULL) {
            mapset[x][y].insert(node->val);
            depthFirstSearch(node->left, x - 1, y + 1, mapset);
            depthFirstSearch(node->right, x + 1, y + 1, mapset);
        }
    }
};

Ссылки

• Дополнительные сведения см. На Доске обсуждения , на которой вы можете найти множество хорошо объясненных принятых решений на различных языках. включая эффективные алгоритмы и асимптотики c время / пространство анализ сложности ^{1 , 2} .