平展二叉树 - >单链表（红宝石）

我正在研究一种递归算法，将二叉树平铺成单链表。问题陈述：平展二叉树 - >单链表（红宝石）

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

平展二叉树 - >单链表（红宝石）

回答

相关问题