Question: https://oj.leetcode.com/problems/flatten-binary-tree-to-linked-list/
Question Name: Flatten Binary Tree to Linked List
The recursive method is easy to understand.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | # Definition for a binary tree node # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: # @param root, a tree node # @return root, a tree node def flattenHelper(self, root): if root == None: return None else: left = root.left right = root.right root.left = None # Truncate the left subtree current = root # Flatten the left subtree current.right = self.flattenHelper(left) while current.right != None: current = current.right # Flatten the right subtree current.right = self.flattenHelper(right) return root # @param root, a tree node # @return nothing, do it in place def flatten(self, root): self.flattenHelper(root) return |
The iterative solution should be more efficient.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | # Definition for a binary tree node # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: # @param root, a tree node # @return nothing, do it in place def flatten(self, root): if root == None: return stack = [root.right, root.left] current = root while len(stack) != 0: nextNode = stack.pop() if nextNode == None: continue else: # Truncate the left subtree current.left = None current.right = nextNode current = current.right stack.append(current.right) stack.append(current.left) return |