[Tree]114. Flatten Binary Tree to Linked List

分類:Tree

時間複雑度:O(n)という木のノードを一度遍歴する場合の時間複雑度はO(n)

である.

空間複雑度:O(1)

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:

    1
   / \
  2   5
 / \   \
3   4   6

The flattened tree should look like:

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

コード:

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

class Solution:
    
    prev=None
    
    def flatten(self, root: 'TreeNode') -> 'None':
        """
        Do not return anything, modify root in-place instead.
        """
        if root==None:
            return

        self.flatten(root.right)
        self.flatten(root.left)
        
        root.right=self.prev
        root.left=None
        self.prev=root

ディスカッション:
1.この問題も最初は難しいからできないと思っていたが、説明を見て簡単な問題だった.この問題の説明は公瑾の説明を読んだ.主な考え方は,保存した値をノードの右側に置き,左サブツリーのクリアを行い,prevを更新することである.後序遍歴の特徴も考察した.