You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
28 lines
738 B
Ruby
28 lines
738 B
Ruby
# Given a binary tree, convert it to a doubly linked list without creating new nodes.
|
|
#
|
|
# Definition for a binary tree node.
|
|
# class TreeNode
|
|
# attr_accessor :val, :left, :right
|
|
# def initialize(val)
|
|
# @val = val
|
|
# @left, @right = nil, nil
|
|
# end
|
|
# end
|
|
|
|
# @param {TreeNode} root
|
|
# @return {String[]}
|
|
|
|
def binary_tree_to_linked_list(root)
|
|
queue = [root.left, root.right]
|
|
current_node = root
|
|
current_node.left = nil
|
|
|
|
while queue.length > 0
|
|
next_node = queue.shift
|
|
queue << next_node.left if next_node.left
|
|
queue << next_node.right if next_node.right
|
|
current_node.right, next_node.left = next_node, current_node
|
|
current_node = next_node
|
|
end
|
|
end
|