Why it is wrong? Please help!


  • 0
    A

    My solution failed at the last test case, the node order within some of the levels dose not match.

    I do a regular BFS with a rank. for the left child rank -1, for the right child rank +1;
    if the pop node with a rank <0 put it into the res_l, if the rank > 0 put it into res_r;

    at the last reverse res_l and append it with res_r;

    class Solution {
        vector<vector<int>> res_l, res_r;
    public:
        vector<vector<int>> verticalOrder(TreeNode* root) {
            if (!root) {
                return res_r;
            }
            queue<TreeNode*> q_node;
            queue<int> q_rank;
            q_node.push(root);
            q_rank.push(0);
            TreeNode *cur;
            int rank;
            while (!q_node.empty()) {
                cur = q_node.front();
                q_node.pop();
                rank = q_rank.front();
                q_rank.pop();
                if (rank>=0) {
                    while (res_r.size() <= rank) {
                        res_r.emplace_back(0);
                    }
                    res_r[rank].push_back(cur->val);
                } else {
                    int idx = -rank - 1;
                    while (res_l.size() <= idx) {
                        res_l.emplace_back(0);
                    }
                    res_l[idx].push_back(cur->val);
                }
                if (cur->left) {
                    q_node.push(cur->left);
                    q_rank.push(rank-1);
                }
                if (cur->right) {
                    q_node.push(cur->right);
                    q_rank.push(rank+1);
                }
            }
            assert(q_rank.empty());
            int i = 0, j = res_l.size()-1;
            while (i<j) swap(res_l[i++],res_l[j--]);
            res_l.insert(res_l.end(), res_r.begin(), res_r.end());
            return res_l;
        }
    };

  • 0
    D

    Same with me... failed at the last test case..


  • 0

    Sorry, I have just fixed the issue. Please submit again, your code should get Accepted now.


  • 0
    A

    Thanks! It works!


Log in to reply
 

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