垂直打印二叉树

Question

我想垂直打印一棵二叉树。我知道一个使用hashmap的解决方案。但是，我在许多地方读到，它可以通过使用双链接列表来完成。但是，我搞不懂怎么做。我在网上也找不到任何可以理解的材料。有人能帮我一下双链接列表方法吗？

示例：

        5
    4       3
  6   7   8   9

这给了我们

6
4
5 7 8
3
9

也就是说，它就像一个垂直顺序的水平顺序遍历。

使用散列映射的解决方案:假设根被索引为0，那么左边的将是-1、-2等，右边的将是+1、+2等。因此，我们可以在列号上构建一个散列键，并有一个以该特定列号为值的所有根的列表。然后我们可以简单地在散列中打印条目。

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

我在其他许多地方也发现了同样的评论。

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)

Answer 2

以下是我在目标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);
    }
}