Flatten Binary Tree to Linked List
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
URL: 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 root == None:
return root
stack = []
current = root
while((stack != []) or (current != None)):
if current.right != None:
stack.append(current.right)
if current.left != None:
current.right = current.left
current.left = None
else:
if stack != []:
temp = stack.pop()
current.right = temp
current = current.right