垂直打印二叉树

Question

我想要竖着打印一棵二叉树。我知道可以使用哈希表来解决这个问题。但是，我在很多地方都看到说可以使用双向链表来实现。然而，我无法理解如何做到这一点。我也没有在网上找到任何易于理解的材料。有人能帮我使用双向链表方法吗？

示例：

        5
    4       3
  6   7   8   9

这提供了

6
4
5 7 8
3
9

使用哈希映射的解决方案：假设根节点的索引为0，则左侧节点将是-1，-2等，右侧节点将是+1，+2等。因此，我们可以建立一个以列号为键的哈希表，并将该特定列号作为值具有该列号的所有根节点的列表。然后，我们可以简单地打印哈希表中的条目。

请参见此链接，阅读第一轮技术问题1的评论。

我在许多其他地方也看到了类似的评论。

- user2714358

---

定义“纵向打印”，并描述您的哈希映射解决方案，还请提供有关双向链表的讨论链接。 - Niklas B.

给定一个字符字符串，显示出在该字符串中出现多次的字符。你可以逐个遍历每个字符，使用一个char,int类型的map，将所有字符存入map中，最后打印出所有出现次数大于1的键值。当然，在C++中你可以使用map，但任何关联容器都可以。 - user2485710

“5 4 3 6 7 8 9” 没有排序。如果我对其进行排序并构建一棵树，我不知道你是如何得到 “6 4 5 7 8 3 9” 的。 - Niklas B.

@NiklasB. 为什么你需要对它进行排序？只需填写级别即可。将其视为级别顺序遍历。 - user2714358

我认为你的方法很好。如果它能够正常工作，就不需要改变它。在我看来，哈希映射是最明显和清晰的解决方案。 - Niklas B.

Answer 1

面试官可能想要让您将一个链表传递到树中，并为每个节点指定指向表示其列的列表元素的指针。

想象一下链表在两个方向上都是无限的，当您碰到末尾时，您可以轻松地扩展它。列表的每个项目依次是节点列表：

function traverse(tree_node, list_node):
    if tree_node is NIL:
        return
    list_node.add(tree_node)
    traverse(tree_node.left, list_node.prev)
    traverse(tree_node.right, list_node.next)

- Niklas B.

---

认为这是正确的。谢谢！ :) - user2714358

@MukulJain在这种情况下，该算法将输出“[[n2]，[n1，n3]，[n4]]”，我认为这是正确的。 - Niklas B.

有人能否解释一下这个，因为我无法清楚地理解它。 - Ankush Dutt

Answer 2

这是我的基于双向链表的Objective-C解决方案：

#import <Foundation/Foundation.h>
#import <stdio.h>

@interface ListNode : NSObject

+ (ListNode *)nodeWithValue:(id)value next:(ListNode *)next previous:(ListNode *)previous;

@property (nonatomic, strong) ListNode *next;
@property (nonatomic, strong) ListNode *previous;
@property (nonatomic, strong) id value;
@end

@implementation ListNode

+ (ListNode *)nodeWithValue:(id)value next:(ListNode *)next previous:(ListNode *)previous
{
    ListNode *node = [[ListNode alloc] init];
    node.value = value;
    node.previous = previous;
    node.next = next;
    return node;
}

@end


@interface TreeNode : NSObject

+ (TreeNode *)nodeWithValue:(id)value left:(TreeNode *)left right:(TreeNode *)right;

@property (nonatomic, strong) TreeNode *left;
@property (nonatomic, strong) TreeNode *right;
@property (nonatomic, strong) id value;
@end

@implementation TreeNode

+ (TreeNode *)nodeWithValue:(id)value left:(TreeNode *)left right:(TreeNode *)right
{
    TreeNode *node = [[TreeNode alloc] init];
    node.value = value;
    node.left = left;
    node.right = right;
    return node;
}

@end

ListNode *verticalTraversal(TreeNode *node, ListNode *list)
{
    if (!node) {
        return list;
    }

    [((NSMutableArray *)list.value) addObject:node.value];

    ListNode *head = list;
    if (node.left) {
        if (!list.previous) {
            list.previous = [ListNode nodeWithValue:[NSMutableArray array] next:list previous:nil];
        }

        head = verticalTraversal(node.left, list.previous);
    }

    if (node.right) {
        if (!list.next) {
            list.next = [ListNode nodeWithValue:[NSMutableArray array] next:nil previous:list];
        }

        verticalTraversal(node.right, list.next);
    }

    return head;
}

void verticalPrint(TreeNode *root)
{
    ListNode *list = [ListNode nodeWithValue:[NSMutableArray array] next:nil previous:nil];
    ListNode *head = verticalTraversal(root, list);
    ListNode *next = head;
    NSInteger level = 0;
    while (next) {
        NSArray *array = (NSArray *)(next.value);
        NSLog(@"%li: %@", level, [array componentsJoinedByString:@", "]);
        next = next.next;
        level ++;
    }
}

int main (int argc, const char * argv[])
{
    @autoreleasepool {
        TreeNode *tree = [TreeNode nodeWithValue:@1
                                            left:[TreeNode nodeWithValue:@2 left:[TreeNode nodeWithValue:@4 left:nil right:nil] right:[TreeNode nodeWithValue:@5 left:nil right:nil]]
                                           right:[TreeNode nodeWithValue:@3 left:[TreeNode nodeWithValue:@6 left:nil right:nil] right:[TreeNode nodeWithValue:@7 left:nil right:nil]]];

        verticalPrint(tree);
    }
}

- Valentin Shergin