Leetcode Flatten Binary Tree to Linked List problem solution

YASH PAL,

In this Leetcode Flatten Binary Tree to Linked List problem solution we have Given the root of a binary tree, flatten the tree into a “linked list”:

  1. 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.
  2. The “linked list” should be in the same order as a pre-order traversal of the binary tree.
Leetcode Flatten Binary Tree to Linked List problem solution

Problem solution in Python.

def flatten(self, root):
    if not root: return
    left, right = root.left, root.right
    self.flatten(left)
    self.flatten(right)
    root.left = None
    if left:
        root.right = left
        while root.right:
            root = root.right
    root.right = right

Problem solution in Java.

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

Problem solution in C++.

class Solution {
private:
    TreeNode* flatTree(TreeNode *root) {
        if(!root->left && !root->right) return root;
        if(!root->right) {
            root->right = root->left;
            root->left = NULL;
            return flatTree(root->right);
        }
        if(!root->left) return flatTree(root->right);
        TreeNode* oldRight = root->right;
        root->right = root->left;
        (flatTree(root->right))->right = oldRight;
        root->left = NULL;
        return flatTree(root->right);
    }
public:
    void flatten(TreeNode *root) {
        if(!root) return;
        flatTree(root);
    }
};

Problem solution in C.

struct TreeNode* prev = NULL;

void flatten(struct TreeNode* root){
    if (root == NULL){
        return;
    }
    flatten(root->right);
    flatten(root->left);
    root->right = prev;
    root->left = NULL;
    prev = root;
}

coding problems