LeetCode知识点总结 - 114

LeetCode 114. Flatten Binary Tree to Linked List

题目

Given the root of a binary tree, flatten the tree into a “linked list”:

The “linked list” should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.
The “linked list” should be in the same order as a pre-order traversal of the binary tree.

思路

如果curr有left child, 把right subtree移到左边:

1 先找到left subtree右边分叉的最下面一个node p
2 把curr.right移动到p.right
3 把curr.left移到curr.left

答案

class Solution:
    def flatten(self, root: TreeNode) -> None:
        curr = root
        
        while curr:
            if curr.left != None:
                p = curr.left
                while p.right != None:
                    p = p.right
                    
                p.right = curr.right
                
                curr.right = curr.left
                curr.left = None
            
            curr = curr.right
        

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18