Flatten Binary Tree to Linked List

1. Problem Description

Given the root root of a binary tree, flatten it into a singly linked list:

The flattened list should still use TreeNode, where the right pointer points to the next node and the left pointer is always null. The flattened list should follow the same order as the binary tree’s preorder traversal.

2. Approach

1. Approach 1
   • Save the preorder traversal into an array
   • Modify the left and right pointers of each element in the array
2. Approach 2
   1. Postorder traversal
3. Approach 3
   1. Keep the previous node while doing preorder traversal

3. Implementation

3.1. Approach 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. Approach 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. Approach 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. References

• 114. Flatten Binary Tree to Linked List - LeetCode
• Detailed Analysis and Multiple Solutions - LeetCode