Leetcode114. Expand binary tree into linked list

1、 Title Description
Give you the root node of the binary tree root , Please expand it into a single linked list ：

• The expanded single linked list should also be used TreeNode , among right The child pointer points to the next node in the list , The left sub pointer is always null .
• The expanded single linked list should be the same as the binary tree The first sequence traversal Same order .

Example 1：

Input ：root = [1,2,5,3,4,null,6]
Output ：[1,null,2,null,3,null,4,null,5,null,6]

Scheme 1 Preorder traversal and expansion are carried out separately

Their thinking ：
First, we can use a list Save the result of the preorder traversal . And then to list Of elements in right Pointer operation .

The code is as follows

class Solution {
    
    public void flatten(TreeNode root) {
    
        List<TreeNode> list = new ArrayList<TreeNode>();
        preorderTraversal(root, list);
        int size = list.size();
        for (int i = 1; i < size; i++) {
    
            TreeNode prev = list.get(i - 1), curr = list.get(i);
            prev.left = null;
            prev.right = curr;
        }
    }

    public void preorderTraversal(TreeNode root, List<TreeNode> list) {
    
        if (root != null) {
    
            list.add(root);
            preorderTraversal(root.left, list);
            preorderTraversal(root.right, list);
        }
    }
}

Option two

It can be found that the order of expansion is actually the first order traversal of binary tree . Algorithm and 94 In the question, the order traverses Morris The algorithm is a bit like , We need to finish the problem in two steps .

1. Insert the left subtree into the right subtree
2. Connect the original right subtree to the rightmost node of the left subtree
3. Consider the root node of the new right subtree , Repeat the above process all the time , Until the new right subtree is null

You can see the picture to understand the process .

    1
   / \
  2   5
 / \   \
3   4   6

// take  1  Where the left subtree of is inserted into the right subtree 
    1
     \
      2         5
     / \         \
    3   4         6        
// Connect the original right subtree to the rightmost node of the left subtree 
    1
     \
      2          
     / \          
    3   4  
         \
          5
           \
            6
            
 // take  2  Where the left subtree of is inserted into the right subtree 
    1
     \
      2          
       \          
        3       4  
                 \
                  5
                   \
                    6   
        
 // Connect the original right subtree to the rightmost node of the left subtree 
    1
     \
      2          
       \          
        3      
         \
          4  
           \
            5
             \
              6         
  
  ......

The code is as follows ：

public void flatten(TreeNode root) {
    
    while (root != null) {
     
        // The left sub tree is  null, Consider the next node directly 
        if (root.left == null) {
    
            root = root.right;
        } else {
    
            //  Find the rightmost node of the left subtree 
            TreeNode pre = root.left;
            while (pre.right != null) {
    
                pre = pre.right;
            } 
            // Connect the original right subtree to the rightmost node of the left subtree 
            pre.right = root.right;
            //  Insert the left subtree into the right subtree 
            root.right = root.left;
            root.left = null;
            //  Consider next node 
            root = root.right;
        }
    }
}