_114. Question 114.md

114. Question 114

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : June 11, 2024

Last updated : July 01, 2024

---

Related Topics : N/A

Acceptance Rate : Unknown

---

Solutions

• m114 v1 Stack.py
• m114 v2 O(1) Space Optimized.c
• m114 v2 O(1) Space.c

Python

m114 v1 Stack.py

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        latestNode = root
        toVisit = [None]
        while latestNode :
            if latestNode.right :
                toVisit.append(latestNode.right)
            if latestNode.left :
                toVisit.append(latestNode.left)
                latestNode.left = None

            latestNode.right = toVisit.pop()
            latestNode = latestNode.right

C

m114 v2 O(1) Space Optimized.c

// Simpler O(1) solution with a lottttt less if statements lol

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


void flatten(struct TreeNode* root) {
    struct TreeNode* current = root;

    bool onlyRightMovements = true;
    while (current) {
        if (current->left) {
            struct TreeNode* temp = current->left;
            while (temp->right) {
                temp = temp->right;
            }
            temp->right = current->right;
            current->right = current->left;
            current->left = NULL;
        } else {
            current = current->right;
        }
    }
}

m114 v2 O(1) Space.c

// O(1) space let's gooooo

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

// I'm gonna try this with O(1) space 
/** Plan:
  * Iterate to the very leftmost node
  * Set the previous node's right to the leftmost and the leftmost's next to the previous right
  * repeat iterating upwards (iterate through the new right branch first)
  */


void flatten(struct TreeNode* root) {
    struct TreeNode* current = root;

    bool onlyRightMovements = true;
    while (current) {
        if (!(current->left) && !(current->right)) {
            if (onlyRightMovements) {
                return;
            } else {
                onlyRightMovements = true;
                current = root;
            }
        } else if (current->left) {
            if (!(current->left->right)) { // next left is leaf
                current->left->right = current->right;
                current->right = current->left;
                current->left = NULL;
                current = current->right;
            } else if (!(current->left->left)) {
                current->left->left = current->left->right;
                current->left->right = NULL;
            } else {
                current = current->left;
                onlyRightMovements = false;
            }
        } else { // only right branch exists
            current = current->right;
        }
    }
}