迭代法实现二叉树Vertical Order Traversal输出错误问题求解

错误原因 #

你的代码核心问题是没有将每个节点和它对应的水平距离（Hd）绑定存储：

• 仅使用了一个全局的Hd变量在遍历过程中反复修改，该变量无法和队列中存储的各个节点做一一对应，最终所有节点都会被错误存入map的同一个key对应的数组中，输出自然就是层序遍历的所有节点排在同一行的结果。

修正方案 #

修改队列的存储结构，让每个入队元素同时保存节点指针和该节点对应的水平距离，逻辑如下：

1. 队列类型改为queue<pair<Node*, int>>，第一个元素存节点指针，第二个存对应Hd
2. 根节点入队时同步存入初始Hd 0
3. 每次弹出队首元素时，先取出该节点的Hd用来写入map，再基于这个Hd计算左右子节点的Hd，和子节点绑定后入队

修正后的完整代码 #

#include <iostream>
#include <map>
#include <queue>
#include <vector>
using namespace std;

struct Node
{
    int data;
    Node *left;
    Node *right;

    Node(int val)
    {
        data = val;
        left = NULL;
        right = NULL;
    }
};

map<int, vector<int>> verticalPrint(Node *root)
{
    // 队列同时存储节点和对应水平距离
    queue<pair<Node*, int>> qi;
    map<int, vector<int>> mp;

    // 根节点初始Hd为0
    qi.push({root, 0});

    while (!qi.empty())
    {
        auto curr = qi.front();
        qi.pop();
        Node* temp = curr.first;
        int hd = curr.second;
        // 用当前节点对应的Hd写入map
        mp[hd].push_back(temp->data);

        if (temp->left != NULL)
        {
            // 左子节点Hd为当前Hd-1，绑定后入队
            qi.push({temp->left, hd - 1});
        }
        if (temp->right != NULL)
        {
            // 右子节点Hd为当前Hd+1，绑定后入队
            qi.push({temp->right, hd + 1});
        }
    }
    return mp;
}

int main()
{
    Node *root = new Node(10);
    root->left = new Node(7);
    root->right = new Node(4);
    root->left->left = new Node(3);
    root->left->right = new Node(11);
    root->right->left = new Node(14);
    root->right->right = new Node(6);

    map<int, vector<int>> mp = verticalPrint(root);

    map<int, vector<int>>::iterator it;

    for (it = mp.begin(); it != mp.end(); it++)
    {
        for (int i = 0; i < it->second.size(); i++)
        {
            cout << it->second[i] << " ";
        }
        cout << endl;
    }

    return 0;
}

运行后即可得到你预期的输出结果。

内容的提问来源于stack exchange，提问作者Jay1105