二叉樹的垂直和

如何找到二叉樹的垂直和。二叉樹的垂直和

例如，考慮下面的二叉樹，

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

對於上述樹，垂直總和應計算如下，

第1行：5
2行： 4
第3行：2,9,1
第4行：5
第5行：1,3,6-
線6：6
線7：3,7,5
線8：7
線9：5

輸出應是：

5,4,12,5,10,6,15,7,5

來源

2012-03-10 Anantha Krishnan

你如何計算總和？它的垂直如何？ – 2012-03-10 13:03:37

我編輯了這個問題。請找到垂直線。 – 2012-03-10 13:14:47

我不清楚垂直線是如何定義的。你能用一個更高層次的樹來展示它嗎？ – svick 2012-03-10 13:37:28

首先，你應該找到的位置，你可以通過計算左和權利開支，以達到特定的節點數量做到這一點：

    1  : l = 0, r = 0 
       /\ 
      / \ 
     l=1,r=0 2  3 : l = 0, r = 1. 
      /\ /\ 
    ... 4...5 6...7 ....

只要你可以穿越你的二叉樹最後計算出LorR = NumberOfLeft - NumberOfRights每個節點，然後組這個數字（通過其LorR值）一起，發現各組總和（它們打印從最積極的到的LorR最負值）。

更新：這對於高度超過兩倍的樹不應答，我們可以在算法中稍加修改來解決此問題。

我們可以看到樹金字塔，金字塔的每個頂點的長度爲1，以後每一個分支其餘分支的一部分，等於什麼最新舉措過去了，我們對此進行了畫面的高度爲3的樹：

    1 
       /\ 
      / \ 
      / \ 
      2  3 upto this we used 1/2 size of pyramid 
      /\ /\ 
     / \ / \ 
      4 5 6 7 upto this we used 1/2 + 1/4 part of pyramid 
     /\/\/\/\ 
     5 9 1 3 6 7 5 5 upto this we used 1/2 + 1/4 + 1/4 part of pyramid

這意味着在每一步中我們都會根據它們的高度來計算左值（實際上每次乘以1/2的倍數都會被添加到左值，除了上次，等於h-1值）。

因此，對於這種情況我們有：1根在組0中，3在葉中是組-1/2 + 1/4 + 1/4 = 0，葉在組6中是1/2 - 1/4 - 1/4 = 0

葉中的1在-1/2 + 1/4 - 1/4 = -1/2等等。

爲防止將1 /（2^x）舍入爲零或其他問題，我們可以將我們的因子（1/2，1/4，1/8，...）乘以2 ^h-1 。事實上，在我寫的第一個案例中，我們可以說因子乘以2 ^2-1。在僞碼

Related Pyramid for tree of height 4

來源

2012-03-10 13:05:35

有趣。檢查你的算法。謝謝。 – 2012-03-10 13:16:40

我認爲你的算法不適用於高度超過2的二叉樹。 – 2012-03-10 13:21:58

我編輯的答案適用於所有情況。 – 2012-03-10 22:22:37

蠻力方法：

columnAdd(tree): 
    sumPerColumn = new Map<int,int>(); 
    traverse(tree.root, sumPerColumn, 0); 
    return sumPerColumn; 

traverse(node, sumPerColumn, currentColumn): 
    sumPerColumn[currentColumn] ++; 
    traverse(node.left, sumPerColumn, currentColumn-1); 
    traverse(node.right, sumPerColumn, currentColumn+1);

這將產生：

{-2: 4, 
    -1: 2, 
    0: 12, 
    1: 3, 
    2: 7}

來源

2012-03-10 13:05:47

我認爲你的意思是'currentColumn - 1'和'currentColumn + 1'，不是'--'和'++'。 – svick 2012-03-10 13:38:22

@svick：是的，這可能更清楚，更「正確」:)。我會改變它。 – 2012-03-10 13:46:41

據我理解向左移動是-1，向右移動是+1 。您可以使用修改後的dfs。這裏是假設add(col, value)定義

dfs(col, node) 
begin 
    add(col, node.value) 
    if(haveLeft) 
    dfs(col-1, left) 
    if(haveRight) 
    dfs(col+1, right) 
end

假設，即添加（1）（使用HashMap的或簡單的陣列例如）爲O作品，這工作在O（N）。

來源

2012-03-10 14:02:35 kilotaras

不錯的解決方案....... – 2012-03-23 19:39:27

二叉樹的垂直和

回答

相關問題