LeetCode 114. 二叉树展开为链表

114. 二叉树展开为链表

Difficulty: 中等

给定一个二叉树，将它展开为一个单链表。

例如，给定二叉树

    1
   /   2   5
 / \   3   4   6

将其展开为：

1
   2
       3
           4
               5
                   6

Solution

Language: 全部题目

右左根序遍历（RLD），这个递归的过程比较难理解，英文区有一个用户画出了RLD遍历的过程，可以参考一下。

    1
   /   2   5
 / \   3   4   6
-----------        
pre = 5
cur = 4

    1
   / 
  2   
 / \   
3   4
           5
               6
-----------        
pre = 4
cur = 3

    1
   / 
  2   
 /   
3 
   4
       5
           6
-----------        
cur = 2
pre = 3

    1
   / 
  2   
       3 
           4
               5
                   6
-----------        
cur = 1
pre = 2

1
   2
       3
           4
               5
                   6

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    prev = None
    def flatten(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        if not root: return 
        # RLD（右左根序遍历）
        self.flatten(root.right)
        self.flatten(root.left)

        root.right = self.prev
        root.left = None
        self.prev = root

LeetCode 114. 二叉树展开为链表

原文：https://www.cnblogs.com/swordspoet/p/14049448.html