二叉树展开为链表

1. 题目描述

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

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

2. 思路

1. 思路一
   • 先序遍历保存到数组中
   • 修改数组中每个元素的前后指针
2. 思路二
   1. 后序遍历
3. 思路三
   1. 先序遍历时保存上一个节点

3. 实现

3.1. 思路一

package main

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func flatten(root *TreeNode) {
	if root == nil {
		return
	}

	res := make([]*TreeNode, 0)
	preOrdered(root, &res)

	for i := 0; i < len(res)-1; i++ {
		res[i].Right = res[i+1]
		res[i].Left = nil
	}

}

func preOrdered(root *TreeNode, res *[]*TreeNode) {
	if root == nil {
		return
	}

	*res = append(*res, root)
	preOrdered(root.Left, res)
	preOrdered(root.Right, res)
}

3.2. 思路二

func flatten(root *TreeNode)  {
    var pre *TreeNode
    dfs(root, &pre)
}

func dfs(root *TreeNode, pre **TreeNode) {
    if root == nil {
        return
    }

    dfs(root.Right, pre)
    dfs(root.Left, pre)
    root.Right = *pre
    root.Left = nil
    *pre = root
}

3.3. 思路三

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */



func flatten(root *TreeNode)  {
    var pre *TreeNode = &TreeNode{}
    dfs(root, &pre)
}

func dfs(root *TreeNode, pre **TreeNode) {
    if root == nil {
        return
    }
    
    left := root.Left
    right := root.Right

    (*pre).Right = root
    (*pre).Left = nil
    *pre = root

    dfs(left, pre)
    dfs(right, pre)
}

4. 参考

• 114. 二叉树展开为链表 - 力扣（LeetCode）
• 详细通俗的思路分析，多解法 - 二叉树展开为链表 - 力扣（LeetCode）