114. 二叉树展开为链表

题目

给你二叉树的根结点 root ，请你将它展开为一个单链表：

• 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
• 展开后的单链表应该与二叉树 先序遍历 顺序相同。

难度：🌟🌟🌟

示例 1：

输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [0]
输出：[0]

提示：

• 树中结点数在范围 [0, 2000] 内
• -100 <= Node.val <= 100

题解

思路一：最简单的思路是先先序遍历，然后根据先序遍历结果构造链表。

思路二：递归

1. 将root的左子树和右子树拉平
2. 将root的右子树接到左子树下方，然后将整个左子树作为右子树
   

代码实现

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func flatten(root *TreeNode) {
	if root == nil {
		return
	}
	p := root
	res := preorder(root)
	for i := 1; i < len(res); i++ {
		next := &TreeNode{
			Val:  res[i],
			Left: nil,
		}
		p.Right = next
		p.Left = nil
		p = p.Right
	}
	return
}

func preorder(root *TreeNode) (res []int) {
	if root == nil {
		return nil
	}
	var preorderHelper func(node *TreeNode)
	preorderHelper = func(node *TreeNode) {
		if node == nil {
			return
		}
		res = append(res, node.Val)
		preorderHelper(node.Left)
		preorderHelper(node.Right)
	}
	preorderHelper(root)
	return
}

// 递归方式展开链表
func flatten(root *TreeNode) {
	if root == nil {
		return
	}
	flatten(root.Left)
	flatten(root.Right)
	left := root.Left
	right := root.Right
	// 将 root 的左子树和右子树拉平
	root.Left = nil
	root.Right = left
	// 将 root 的右子树接到左子树下方，然后将整个左子树作为右子树
	p := root
	for p.Right != nil {
		p = p.Right
	}
	p.Right = right
	return
}