[LeetCode] 114. Flatten Binary Tree to Linked List

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

For example, given the following tree:

The flattened tree should look like:

这个题思路就是DFS, 先左后右, 记住如果是用stack如果需要先得到左, 那么要先append右, 另外需要注意的就是用recursive方式的时候需要用一个temp来去存root.right, 否则用preorder的时候root.right就是丢了!

1. Constraints

1) can be empty

2. Ideas

DFS T: O(n) S:O(1)

用pre来存之前的node, 然后DFS

3. Code

3.1) iterable

 class Solution:

     def flatten(self, root):

         pre, stack = None, [root]

         while stack:

             node = stack.pop()

             if node:

                 if pre:

                     pre.left = None  # dont forget to set left as None

                     pre.right = node

                 pre = node

                 stack.append(node.right) # stack 先进后出

                 stack.append(node.left)

3.2) recursive

 class Solution:

     def __init__(self):

         self.pre = None

     def flatten(self, root):

         if not root: return

         if self.pre:

             self.pre.left = None

             self.pre.right = root

         self.pre = root

         temp = root.right  # otherwise we will lose the root.right

         self.flatten(root.left)

         self.flatten(root.right)

4. Test cases

1) None

巴特西

[LeetCode] 114. Flatten Binary Tree to Linked List_Medium tag: DFS

最新文章

热门文章