list - 如何使用双链表找到二叉树的垂直和？

Question

给定一棵二叉树，我们如何使用双向链表有效地找到每个垂直级别的总和.. 是的，我知道我们可以使用哈希表找到它...但是如何使用双向链表请用代码和示例解释！提前致谢

Answer 1

这就引出了一个问题，“家庭作业？”

node { sum = 0; node *next=NULL; node *prev=NULL; } 

allocate node root_node

dfs(root,root_node){
    root_node.sum++
    if (leftchild) // check whether the child exists in tree
        if (!left_node) // check for left child in linked list
            allocate node left_node
        dfs(leftchild,left_node)
    if (rightchild) // check whether the child exists in tree
        if (!right_node) // check for right child in linked list
            allocate node right_node
        dfs(rightchild,right_node)
}

PS：我不会完整地回答这个问题（即举例），因为我认为这很有可能是一个家庭作业问题。

Answer 2

这是Java实现

public static Collection<Integer> verticalSumUsingDLL(BinaryTreeNode<Integer> node) {
    if (node == null) {
        return Collections.emptyList();
    }
    LinearNode<Integer> head = new LinearNode<Integer>(node.getData());
    verticalSumUsingDLL(head, node);
    List<Integer> result = new ArrayList<Integer>();

    while(head.prev != null) {
        head = head.prev;
    }

    while (head != null) {
        result.add(head.data);
        head = head.next;           
    }
    return result;
}

private static void verticalSumUsingDLL(LinearNode<Integer> dll, BinaryTreeNode<Integer> node) {
    if (node == null) {
        return ;
    }
    if (node.hasLeftChild()) {
        if (dll.prev == null) {
            LinearNode<Integer> temp = new LinearNode<Integer>(node.getLeft().getData());
            dll.prev = temp;
            temp.next = dll;
        } else {
            dll.prev.data = dll.prev.data + node.getLeft().getData();
        }
        verticalSumUsingDLL(dll.prev, node.getLeft());
    }
    if (node.hasRightChild()) {
        if (dll.next == null) {
            LinearNode<Integer> temp = new LinearNode<Integer>(node.getRight().getData());
            dll.next = temp;
            temp.prev = dll;
        } else {
            dll.next.data = dll.next.data + node.getRight().getData();
        }
        verticalSumUsingDLL(dll.next, node.getRight());
    }

}

这是单元测试用例

@Test
public void verticalSumUsingDLLOfBinaryTreeTest() {
    BinaryTreeNode<Integer> node = BinaryTreeUtil.<Integer>fromInAndPostOrder(new Integer[]{4,2,5,1,6,3,7}, new Integer[]{4,5,2,6,7,3,1});

    Collection<Integer> verticalSum = BinaryTreeUtil.verticalSumUsingDLL(node);

    assertThat(verticalSum.toArray(new Integer[0]), equalTo(new Integer[]{4,2,12,3,7}));
}