给定二叉树中的垂直和

Question

给定二叉树,找到同一垂直线上的节点的垂直和.通过不同的垂直线打印所有总和.

要了解同一垂直线是什么,我们需要先定义水平距离.如果两个节点具有相同的水平距离(HD),则它们位于同一垂直线上.HD的想法很简单.根的HD为0,右边缘(连接到右子树的边缘)被认为是+1水平距离而左边缘被认为是-1水平距离.例如,在上面的树中,节点4的HD为-2,节点2的HD为-1,5和6的HD为0,节点7的HD为+2.

例子:

    1
  /   \
 2     3
/ \   / \
4  5  6  7

树有5条垂直线

Vertical-Line-1只有一个节点4 => vertical sum是4

Vertical-Line-2:只有一个节点2 =>垂直和是2

Vertical-Line-3:有三个节点:1,5,6 =>垂直和是1 + 5 + 6 = 12

Vertical-Line-4:只有一个节点3 =>垂直和为3

Vertical-Line-5:只有一个节点7 =>垂直和是7

因此预期产量为4,2,12,3和7

我的解决方案: 我想出了这个问题的ao(nlong(n))解决方案.这个想法是:

(1)使用preorder遍历获取每个节点的HD,并将HD及其相关节点存储在一个数组中.

(2)通过HD对数组进行排序

(3)遍历排序数组以打印结果.

我敢肯定这不是解决这个问题的最好方法.有人能帮我提供更好的解决方案吗？

Answer 1

你不能在第一次遍历中完成所有工作吗？定义从HD到sum的字典(哈希映射).对于您访问的每个节点,将其值添加到正确的字典键 - 这是一个O(n)解决方案.

d = {}

def traverse(node, hd):
  if not node:
    return
  if not hd in d:
    d[hd] = 0
  d[hd] = d[hd] + node.value
  traverse(node.left, hd - 1)
  traverse(node.right, hd + 1)

然后打电话 traverse(root, 0)