My Solution:

Use auxiliary list.

python

# 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:
    def flatten(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        # dummy solution
        if not root:
            return []
        auxiliary = []
        def preorder(root):
            if not root:
                return
            auxiliary.append(root)
            preorder(root.left)
            preorder(root.right)
        preorder(root)
        # print(list(map(lambda x: x.val, auxiliary)))
        dummy = TreeNode()
        cur = dummy
        for i in range(len(auxiliary)):
            cur.right = auxiliary[i]
            cur.left = None
            cur = auxiliary[i]
        return dummy.right

Iteration

python

# 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:
    def flatten(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        while root:
            # pre左子树最右下的节点
            pre = root.left
            # 没有左子树，跳过这个循环
            if not pre:
                root = root.right
                continue
            while pre.right:
                pre = pre.right
            pre.right = root.right
            root.right = root.left
            root.left = None
            # 下一个节点
            root = root.right

可以发现展开的顺序其实就是二叉树的先序遍历。算法和 94 题中序遍历的 Morris 算法有些神似，我们需要两步完成这道题。

将左子树插入到右子树的地方将原来的右子树接到左子树的最右边节点考虑新的右子树的根节点，一直重复上边的过程，直到新的右子树为 null 可以看图理解下这个过程。

python

    1
   / \
  2   5
 / \   \
3   4   6

//将 1 的左子树插入到右子树的地方
    1
     \
      2         5
     / \         \
    3   4         6
//将原来的右子树接到左子树的最右边节点
    1
     \
      2
     / \
    3   4
         \
          5
           \
            6

 //将 2 的左子树插入到右子树的地方
    1
     \
      2
       \
        3       4
                 \
                  5
                   \
                    6

 //将原来的右子树接到左子树的最右边节点
    1
     \
      2
       \
        3
         \
          4
           \
            5
             \
              6

  ......

代码的话也很好写，首先我们需要找出左子树最右边的节点以便把右子树接过来。

作者：windliang 链接：https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/solutions/17274/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by--26/ 来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。