Leetcode Study Day 35

Flatten Binary Tree to Linked List

Given the root of a binary tree, flatten the tree into a “linked list”:

The “linked list” should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.
The “linked list” should be in the same order as a pre-order traversal of the binary tree.

Example 1:


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

Input: root = []
Output: []
Example 3:

Input: root = [0]
Output: [0]

Solution

I found this smart solution from Leetcode.

Full code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void flatten(TreeNode* root) {
        // if current node is not empty
        if(root){
            // store right node, and move left to right
            TreeNode *temp = root -> right;
            root -> right = root -> left;
            // set left to nullptr
            root -> left = nullptr;
            // find the end of right node
            TreeNode *currentNode = root;
            while(currentNode -> right)
                currentNode = currentNode -> right;
            // Connect temp at the end of right node
            currentNode -> right = temp;
            // mvoe to the next right node
            flatten(root->right);
        }
        return;
    }
};

Understand

To understand this method better, I asked ChatGPT to draw a procedure diagram for me. Here is the result:

Given the input binary tree root = [1,2,5,3,4,null,6], the tree structure would initially look like this:

    1
   / \
  2   5
 / \   \
3   4   6

Here’s how the flatten function would process this tree step-by-step:

Initial call with root (node 1):

Moves left (node 2) to right.
Sets left to nullptr.
Now the tree looks like this:

1
 \
  2
 / \
3   4

Then we add the right subtree (node 5) to the end of the rightmost branch:

1
 \
  2
 / \
3   4
     \
      5
       \
        6

Then we call flatten on the right subtree (node 2), we move left (node 3) to right and move the other nodes to the right child of node 3.

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

Then we find that actually, all the nodes are at the right side, however, the function will continue running, like put the temp(node 5) connect to the end of the node 4, but the result will still be the same.