114. Flatten Binary Tree to Linked List #

Problem #

Given a binary tree, flatten it to a linked list in-place.

For example, given the following tree:

    1
   / \
  2   5
 / \   \
3   4   6

The flattened tree should look like:

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

Problem Summary #

Given a binary tree, flatten it to a linked list in-place.

Solution Ideas #

• The requirement is to “flatten” the binary tree, and put all tree nodes into the right child pointers in preorder traversal order.

• It can be implemented using either recursive or iterative approaches.

• The recursive idea can be thought of this way: traverse a tree in reverse order, that is, first traverse the right child, then traverse the left child, and finally traverse the root node.

            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
  

• You can first imitate the code for preorder traversal and write out the logic for this reverse-order traversal:

    public void flatten(TreeNode root) {
        if (root == null)
            return;
        flatten(root.right);
        flatten(root.left);
    }
  

• After implementing the reverse-order traversal logic, then connect the nodes together:

    private TreeNode prev = null;
      
    public void flatten(TreeNode root) {
        if (root == null)
            return;
        flatten(root.right);
        flatten(root.left);
        root.right = prev;
        root.left = null;
        prev = root;
    }
  

Code #

package leetcode

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

// Solution 1: Iterative
func flatten(root *TreeNode) {
	list, cur := []int{}, &TreeNode{}
	preorder(root, &list)
	cur = root
	for i := 1; i < len(list); i++ {
		cur.Left = nil
		cur.Right = &TreeNode{Val: list[i], Left: nil, Right: nil}
		cur = cur.Right
	}
	return
}

// Solution 2: Recursive
func flatten1(root *TreeNode) {
	if root == nil || (root.Left == nil && root.Right == nil) {
		return
	}
	flatten(root.Left)
	flatten(root.Right)
	currRight := root.Right
	root.Right = root.Left
	root.Left = nil
	for root.Right != nil {
		root = root.Right
	}
	root.Right = currRight
}

// Solution 3: Recursive
func flatten2(root *TreeNode) {
	if root == nil {
		return
	}
	flatten(root.Right)
	if root.Left == nil {
		return
	}
	flatten(root.Left)
	p := root.Left
	for p.Right != nil {
		p = p.Right
	}
	p.Right = root.Right
	root.Right = root.Left
	root.Left = nil
}