使用迭代方法的垂直顺序遍历

Question

我正在尝试使用映射和队列解决二叉树的垂直顺序遍历问题。我确实用递归的方式解决了它，但是我用迭代的方式没有得到相同的答案。

       10
     /    \
    7      4
  /  \    /  \
 3   11  14   6

方法：

首先，我声明了一个整数，用于存储距根节点的水平距离。

水平距离是指从根开始左边的部分会被认为是-1，-2等等，就像一个负X轴，根是原点，从0开始。所以会给出节点7 -1、3 将给出 -2。但是，10、11、14 将被赋予 0，因为它们不远离根节点，而是位于同一位置。向右，距离将变为正数，因此 4 将获得距离 1，6 将获得 2，依此类推。

首先，我在队列中压入根并将水平距离更新为0。之后，我在地图中添加水平距离作为键和根数据作为值。最后，我从队列中弹出根并检查它的左和右 child，如果左或右 child 可用，我将左和右 child 推入队列分别并相应地更新水平距离。然后我对完整的二叉树执行了相同的过程。

然后，我只是遍历了地图的第二部分来得到答案。

The Answer should be :
3 
7 
10 11 14 
4 
6 

The Answer I received is : 
10 7 4 3 11 14 6

这是我的代码：

#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<Node *> qi;
    map<int, vector<int>> mp;

    int Hd = 0;
    qi.push(root);

    while (!qi.empty())
    {
        Node *temp = qi.front();
        mp[Hd].push_back(temp->data);
        qi.pop();

        if (temp->left != NULL)
        {
            qi.push(temp->left);
            Hd -= 1;
        }
        if (temp->right != NULL)
        {
            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;
}

Answer 1

您不能像那样使用单个 Hd 变量。请注意在第一次迭代中，Hd 将变为 -1 并返回 0，因为根节点同时具有左右子节点。所以在下一次迭代中你再次从 0 开始，但是你从队列中拉出的节点与 Hd.

的值无关

而是将对放入队列：节点及其对应水平距离的组合。然后它将正常工作：

map<int, vector<int>> verticalPrint(Node *root)
{
    queue<pair<int, Node *>> qi;
    map<int, vector<int>> mp;

    qi.push({0, root});

    while (!qi.empty())
    {
        pair<int, Node*> item = qi.front();
        int hd = item.first;
        Node * temp = item.second;
        mp[hd].push_back(temp->data);
        qi.pop();

        if (temp->left != NULL)
        {
            qi.push({hd - 1, temp->left});
        }
        if (temp->right != NULL)
        {
            qi.push({ hd+1, temp->right});
        }
    }
    return mp;
}

使用迭代方法的垂直顺序遍历

Vertical Order Traversal using Iterative method

c++

queue

maps

binary-tree

vector