Question

Formatted question description: https://leetcode.ca/all/114.html

114	Flatten Binary Tree to Linked List

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

For example,
Given

         1
        / \
       2   5
      / \   \
     3   4   6

The flattened tree should look like:
   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6
click to show hints.

Hints:
If you notice carefully in the flattened tree, each node's right child points to the next node of a pre-order traversal.

@tag-tree

Algorithm

DFS

Use the idea of DFS to find the leftmost child node, then return to its parent node, disconnect its parent node from the right child node, connect the original left child node to the right child node of the parent node, and then connect the original right child node The node is connected to the right child node of the new right child node, and then back to the previous parent node to do the same operation.

Although simple, there are still a few pits

  1. Think of maintaining a tail node. At first, I thought about using stack iteration and pre-order traversal. In fact, one principle is to traverse one at a time and add it to the end. So you must save both left and right, and then add it to the tail
  2. Every time tail is updated, left must be set to null, otherwise it is not the result that all you need is right child

Flatten process:

     1
    / \
   2   5
  / \   \
 3   4   6

     1
    / \
   2   5
    \   \
     3   6
      \    
       4

   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

Iteration

Starting from the root node, first check whether its left child node exists, if it exists, disconnect the root node from its right child node, and connect the left child node and all the structures behind it to the original right child node. Connect the original right child node to the last right child node of the meta left child node.

Code

Java

  • import java.util.Stack;
    
    public class Flatten_Binary_Tree_to_Linked_List {
    
    	/**
    	 * Definition for a binary tree node.
    	 * public class TreeNode {
    	 *     int val;
    	 *     TreeNode left;
    	 *     TreeNode right;
    	 *     TreeNode(int x) { val = x; }
    	 * }
    	 */
        public class Solution {
            public void flatten(TreeNode root) {
    
                // pre-order traversal
                if (root == null) {
                    return;
                }
    
                Stack<TreeNode> sk = new Stack<>();
                sk.push(root);
    
                TreeNode prev = new TreeNode(0);
    
                while (!sk.isEmpty()) {
                    TreeNode current = sk.pop();
    
                    if (current.right != null) {
                        sk.push(current.right);
                    }
                    if (current.left != null) {
                        sk.push(current.left);
                    }
    
                    prev.left = null; // cut off
                    prev.right = current;
    
                    prev = current;
                }
            }
        }
    
    
        public class Solution_recursion {
    
            TreeNode prev = new TreeNode(0);
    
            public void flatten(TreeNode root) {
    
                // pre-order traversal, iteration, then every time stack pop, append to list end
                // maintain the tail node
    
                if (root == null) {
                    return;
                }
    
                TreeNode left = root.left;
                TreeNode right = root.right;
    
                // update tail node
                prev.right = root;
                prev.left = null; // @note@note: this is key, cut off left, or "time limit" error
                prev = root;
    
                if (left != null) flatten(left);
                if (right != null) flatten(right);
    
    
            }
        }
    
    }
    
  • // OJ: https://leetcode.com/problems/flatten-binary-tree-to-linked-list/
    // Time: O(N)
    // Space: O(H)
    class Solution {
        TreeNode* dfs(TreeNode* root) { // returns a pointer to the last node after flattening
            if (!root || (!root->left && !root->right)) return root;
            auto leftLast = dfs(root->left), rightLast = dfs(root->right), left = root->left, right = root->right;
            root->left = nullptr;
            root->right = left ? left : right;
            if (left) leftLast->right = right;
            return right ? rightLast : leftLast;
        }
    public:
        void flatten(TreeNode* root) {
            dfs(root);
        }
    };
    
  • # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution(object):
      def flatten(self, root):
        """
        :type root: TreeNode
        :rtype: void Do not return anything, modify root in-place instead.
        """
    
        def dfs(root):
          if not root:
            return root
    
          left = dfs(root.left)
          right = dfs(root.right)
    
          if not left and not right:
            return root
    
          if right is None:
            root.right = root.left
            root.left = None
            return left
    
          if not left:
            return right
    
          tmp = root.right
          root.right = root.left
          root.left = None
          left.right = tmp
          return right
    
        dfs(root)
    
    

All Problems

All Solutions