平展二叉樹 - >單鏈表（紅寶石）

我正在研究一種遞歸算法，將二叉樹平鋪成單鏈表。問題陳述：平展二叉樹 - >單鏈表（紅寶石）

Given a binary tree, flatten it to a linked list in-place. 

For example, 
Given 

     1 
     /\ 
     2 5 
    /\ \ 
    3 4 6 
The flattened tree should look like: 
    1 
    \ 
    2 
     \ 
     3 
     \ 
     4 
      \ 
      5 
      \ 
      6

我寫了下面的遞歸代碼，根本不起作用（返回錯誤的答案），但爲什麼不我不理解概念。從根開始，我們拼合root.left和root.right。如果root.left存在，那麼root.next（或者在這種情況下，root.right）將指向平展的左側列表。然後，左側列表指向右側列表的開頭。這在樹上遞歸地繼續。

這個概念上有什麼問題嗎？我嘗試在前序遍歷之後對它進行建模，因爲根本上訪問了root，然後離開了，然後是右側。

def flatten(root) 
    return root if root.nil? 
    left_list = flatten(root.left) 
    right_list = flatten(root.right) 
    root.left = nil 


    root.right = (left_list.nil? ? right_list : left_list) 
    find_tail(left_list).right = right_list unless left_list.nil? 
end 

def find_tail(node) 
    return nil if node.nil? 
    until node.right.nil? 
     node = node.right 
    end 

    node 
end

來源

2017-02-21 Sunny

「不起作用」是什麼意思？它會崩潰嗎？它會產生錯誤的輸出嗎？它是否在一段合理的時間後終止？ – kraskevich

@kraskevich編輯包括。 – Sunny

你的flatten沒有返回它應該的。當你遞歸地調用它的時候很重要。更改爲

... 
    find_tail(left_list).right = right_list unless left_list.nil? 
    root # <-- add this line 
end

來源

2017-02-22 19:16:57 avysk

發生這種情況是因爲，當我扁化root.left併爲root.right = flatten（root.left）設置指針時，root.right沒有指向展開的左列表的根目錄？ – Sunny

是的，確切地說。你的遞歸調用期望'flatten'返回它剛剛變平的子樹的根;然而，「扁平化」並沒有這樣做。 – avysk

平展二叉樹 - >單鏈表（紅寶石）

回答

相關問題