如何使用雙鏈表查找二叉樹的垂直和？

Question

給定一個二叉樹，我們如何纔能有效地使用雙向鏈表找到每個垂直級別的總和.. 是的，我知道我們可以使用哈希表找到它......但如何使用雙鏈表 請用代碼解釋和例子！ 在此先感謝

Answer 1

這引發了一個問題，「功課？」 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})); 
}