Flatten Binary Tree to Linked List

Title: Flatten Binary Tree to Linked List Source: leetcode.com

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

For example,
Given

/ \

2 5

/ \ \

3 4 6

Hints:

If you notice carefully in the flattened tree, each node’s right child points to the next node of a pre-order traversal.

Python solution

''' https://leetcode.com/problems/flatten-binary-tree-to-linked-list/ '''

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def flatten(self, root):
        """
        :type root: TreeNode
        :rtype: void Do not return anything, modify root in-place instead.
        """
        if not root:
            return
        stack = [root]
        while stack:
            node = stack.pop()
            if node.right:
                stack.append(node.right)
            if node.left:
                node.right = node.left
                stack.append(node.left)
                node.left = None
            if not (node.left or node.right) and stack:
                temp = stack.pop()
                node.right = temp
                stack.append(temp)

''' https://leetcode.com/problems/flatten-binary-tree-to-linked-list/ '''

# Definition for a binary tree node.

# class TreeNode(object):

# def __init__(self, x):

# self.val = x

# self.left = None

# self.right = None

class Solution(object):

def flatten(self, root):

"""

:type root: TreeNode

:rtype: void Do not return anything, modify root in-place instead.

"""

if not root:

return

stack = [root]

while stack:

node = stack.pop()

if node.right:

stack.append(node.right)

if node.left:

node.right = node.left

stack.append(node.left)

node.left = None

if not (node.left or node.right) and stack:

temp = stack.pop()

node.right = temp

stack.append(temp)

Rate this post

Coddicted

Flatten Binary Tree to Linked List

Python solution

Leave a Reply Cancel Reply