HomeLeetcode114. Flatten Binary Tree to Linked List - Leetcode Solutions
Leetcode

114. Flatten Binary Tree to Linked List – Leetcode Solutions

Declan Clarke

Description:

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.

Examples:

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 in Python:

To solve this problem of flattening a binary tree into a “linked list” using 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, we can use an in-place approach. We can achieve this by modifying the tree during a pre-order traversal.

Python
class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        # Helper function to perform the flattening
        def flattenTree(node):
            # If the node is None, return None
            if not node:
                return None
            
            # If the node is a leaf, return the node itself
            if not node.left and not node.right:
                return node
            
            # Recursively flatten the left subtree
            leftTail = flattenTree(node.left)
            # Recursively flatten the right subtree
            rightTail = flattenTree(node.right)
            
            # If there was a left subtree, we need to rewire the connections
            if leftTail:
                # The original right subtree is now the right child of the left tail
                leftTail.right = node.right
                # The left subtree is moved to the right
                node.right = node.left
                # Set the left child to None
                node.left = None
            
            # Return the rightmost node after flattening
            return rightTail if rightTail else leftTail
        
        # Start flattening from the root
        flattenTree(root)

Explanation:

  1. TreeNode Class:
    • The TreeNode class defines the structure of a node in the binary tree with attributes val, left, and right.
  2. Solution Class:
    • The Solution class contains the method flatten, which flattens the tree.
  3. flatten Method:
    • The flatten method is the main method that modifies the tree in place. It calls the helper function flattenTree to perform the actual flattening.
  4. flattenTree Helper Function:
    • Base Case: If the current node is None, return None.
    • Leaf Node Check: If the node is a leaf (i.e., no left and right children), return the node itself.
    • Recursive Calls:
      • Recursively flatten the left subtree and get the tail of the flattened left subtree (leftTail).
      • Recursively flatten the right subtree and get the tail of the flattened right subtree (rightTail).
    • Rewire Connections:
      • If there was a left subtree, perform the following steps:
        • Set the leftTail‘s right child to the original right child of the current node.
        • Move the left subtree to the right by setting node.right to node.left.
        • Set the left child of the current node to None.
    • Return:
      • Return the rightmost node after flattening, which is either rightTail if it exists, otherwise leftTail.

This solution ensures that the tree is modified in place with O(1) extra space, achieving the desired “linked list” in the same order as a pre-order traversal.

Solution in Javascript:

JavaScript
/**
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */
var flatten = function(root) {
    // Helper function to perform the flattening
    const flattenTree = (node) => {
        // If the node is null, return null
        if (node === null) {
            return null;
        }

        // If the node is a leaf, return the node itself
        if (node.left === null && node.right === null) {
            return node;
        }

        // Recursively flatten the left subtree
        let leftTail = flattenTree(node.left);
        // Recursively flatten the right subtree
        let rightTail = flattenTree(node.right);

        // If there was a left subtree, we need to rewire the connections
        if (leftTail !== null) {
            // The original right subtree is now the right child of the left tail
            leftTail.right = node.right;
            // The left subtree is moved to the right
            node.right = node.left;
            // Set the left child to null
            node.left = null;
        }

        // Return the rightmost node after flattening
        return rightTail !== null ? rightTail : leftTail;
    };

    // Start flattening from the root
    flattenTree(root);
};

Solution in Java:

Java
class Solution {
    public void flatten(TreeNode root) {
        // Helper function to perform the flattening
        flattenTree(root);
    }
    
    private TreeNode flattenTree(TreeNode node) {
        // If the node is null, return null
        if (node == null) {
            return null;
        }

        // If the node is a leaf, return the node itself
        if (node.left == null && node.right == null) {
            return node;
        }

        // Recursively flatten the left subtree
        TreeNode leftTail = flattenTree(node.left);
        // Recursively flatten the right subtree
        TreeNode rightTail = flattenTree(node.right);

        // If there was a left subtree, we need to rewire the connections
        if (leftTail != null) {
            // The original right subtree is now the right child of the left tail
            leftTail.right = node.right;
            // The left subtree is moved to the right
            node.right = node.left;
            // Set the left child to null
            node.left = null;
        }

        // Return the rightmost node after flattening
        return rightTail != null ? rightTail : leftTail;
    }
}

Solution in C#:

C#
public class Solution {
    public void Flatten(TreeNode root) {
        // Call the helper function to flatten the tree
        FlattenTree(root);
    }

    private TreeNode FlattenTree(TreeNode node) {
        // If the node is null, return null
        if (node == null) {
            return null;
        }

        // If the node is a leaf, return the node itself
        if (node.left == null && node.right == null) {
            return node;
        }

        // Recursively flatten the left subtree
        TreeNode leftTail = FlattenTree(node.left);
        // Recursively flatten the right subtree
        TreeNode rightTail = FlattenTree(node.right);

        // If there was a left subtree, we need to rewire the connections
        if (leftTail != null) {
            // The original right subtree is now the right child of the left tail
            leftTail.right = node.right;
            // The left subtree is moved to the right
            node.right = node.left;
            // Set the left child to null
            node.left = null;
        }

        // Return the rightmost node after flattening
        return rightTail != null ? rightTail : leftTail;
    }
}

Related Post

Subscribe
Notify of

0 Comments
Oldest
Newest Most Voted
Inline Feedbacks
View all comments

Popular

© 2024 Devexplain.com