algorithm - 打印所有具有相对位置的根到叶路径

Question

给定一棵二叉树，我们如何打印根到叶路径，但添加“_”来指示相对位置？

例子:

Input : Root of below tree
         A 
       /   \  
      B      C 
     / \    / \
    D   E   F  G

Output : All root to leaf paths
_ _ A
_ B
D

_ A
B
_ E

 A
 _ C
 F

A
_ C
_ _ G

Answer 1

您可以使用预订旅行来参观这棵树。用缩进记录路径。

访问左 child 时减少缩进，访问右 child 时增加缩进。然后你就可以得到这样的路径，

(0, A), (-1, B), (-2, D)
(0, A), (-1, B), (0, E)
...

在输出阶段，对路径进行归一化，找到路径节点的最小缩进并将路径节点移动到，

(2, A), (1, B), (0, D)
(1, A), (0, B), (1, E)
...

然后相应地打印路径。

这是python中的示例代码，

def travel(node, indent, path):
    if not node:
        print_path(path)
        return
    path.append((indent, node))
    if node.left:
        travel(node.left, indent - 1, path)
    if node.right:
        travel(node.right, indent + 1, path)
    del path[-1]


def print_path(path):
    min_indent = abs(min([x[0] for x in path]))
    for indent, node in path:
        p = []
        for x in xrange(min_indent + indent):
            p.append('_')
        p.append(node.val)
        print ' '.join(p)