Two Clean C++ Solutions: BFS and DFS


  • 2
    F
    ///BFS, O(n) Space, O(n) Time, longer to write tho
    class Solution {
    public:
        vector<vector<int>> verticalOrder(TreeNode* root) {
            queue<pair<TreeNode *, list<vector<int>>::iterator>> q;
            vector<vector<int>> result;
            if (root == nullptr)
                return result;
            list<vector<int>> buffer;
            buffer.emplace_back();
            q.emplace(root, buffer.begin());
            while (q.size())
            {
                auto cur = q.front();q.pop();
                auto iter = cur.second;
                auto node = cur.first;
                iter->push_back(node->val);
                if (node->left)
                {
                    if(iter == buffer.begin())
                        buffer.emplace_front();
                    q.emplace(node->left, prev(iter));
                }
                if (node->right)
                {
                    if(next(iter) == buffer.end())
                        buffer.emplace_back();
                    q.emplace(node->right, next(iter));
                }
            }
            copy(buffer.begin(), buffer.end(), back_inserter(result));
            return result;
        }
    };
    /// DFS, O(n) Sapce and O(nlgn) Time, a little bit slower but easier to write.
    class Solution {
        map<int, map<int, vector<int>>> table;
        void dfs(TreeNode * root, int i, int j)
        {
            if (root == nullptr)
                return;
            table[j][i].push_back(root->val);
            dfs(root->left, i + 1, j - 1);
            dfs(root->right, i + 1, j + 1);
        }
    public:
        vector<vector<int>> verticalOrder(TreeNode* root) {
            dfs(root, 0, 0);
            vector<vector<int>> result;
            for (const auto & col : table)
            {
                result.emplace_back();
                for (const auto & elem : col.second)
                {
                    const auto & vec = elem.second;
                    copy(vec.begin(), vec.end(), back_inserter(result.back()));
                }
            }
            return result;
        }
    };

  • 1
    W

    @fentoyal Great DFS solution! Sharing some thinkings on when to use BFS or DFS

    • If the tree is balanced, use DFS or BFS

    • If not balanced, use BFS, because DFS use bigger stack, and preallocated 2D matrix will have many entries empty (I am not talking about your solution, I am talking about others' solution).


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.