## Question

>[Leetcode.226 Invert Binary Tree
](https://leetcode.com/problems/invert-binary-tree/)

<br>

:::info
:::spoiler *Optimal Space & Time Complexity*
<br>

- Time complexity: O()
- Space complexity: O()

:::

<br>

## Thoughts & Solutions

### YC
- use "stack"
:::spoiler Code

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */

// Time - log(n) | Space - log(n)
var invertTree = function(root) {
    /** stack + dfs
        1. if(stack.length)
        2. pop the item from the stack
        3. push left child and right child into the stack
        4. swap the left child and right child

        stack          tree
        [4]            4  ->  2, 7  ->  1, 3, 6, 9
        [2, 7]         4  ->  7, 2  ->  6, 9, 1, 3   
        [2, 6, 9]      4  ->  7, 2  ->  9, 6, 1, 3
        [2, 6]         4  ->  7, 2  ->  9, 6, 1, 3
        [2]            4  ->  7, 2  ->  9, 6, 1, 3
        [1, 3]         4  ->  7, 2  ->  9, 6, 3, 1
        [1]            4  ->  7, 2  ->  9, 6, 3, 1
        []             4  ->  7, 2  ->  9, 6, 3, 1
    */
    const stack = [root];
    while(stack.length){
        const node = stack.pop()
        if(!node) continue;
        stack.push(node.left);
        stack.push(node.right);
        [node.left, node.right] = [node.right, node.left]
    }

    return root
};

:::

<hr/>

### Sol

:::spoiler queqe solution

var invertTree = function(root) {
    if(!root) return null;
    const queqe = []
    queqe.push(root)
    let temp = null; // Temporary variable for swapping nodes
    while(queqe.length){
         // Dequeue the first node in the queue
        const node = queqe.shift();
        // Swap the left and right child nodes
        temp = node.left || null;
        node.left = node.right || null;
        node.right = temp;
        // Add the left and right child nodes to the queue if they exist
        if(node.left) {
            queqe.push(node.left)
        };
        if(node.right){
            queqe.push(node.right)   
        }
    }
    return root;
};

:::

<hr/>

### 東
:::spoiler Code

// Time - log(n) | Space - log(n)
var invertTree = function(root) {
    if(!root) {
        return root;
    }
    return swapChildren(root);
};

function swapChildren(parent) {
    if(!parent.left && !parent.right) {
        return parent;
    }
    const temp = parent.left;
    parent.left = parent.right ? swapChildren(parent.right) : null;
    parent.right = temp ? swapChildren(temp): null;
    return parent;
}

:::

<hr/>

### Jessie

:::spoiler Code

:::

<hr/>

### 皮皮

:::spoiler Code

:::

<hr/>

### Howard

:::spoiler Code

class Solution1:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        # Solution 1: recursive, DFS
        # time: O(N)
        # space: O(N) Tree深度，考慮到 callstack space
        # note: 2^N - 1 = depth
        #
        # for example:
        #     (1)
        #  (2)   (3)
        #(4)(5) (6)(7)
        # 走訪的順序是 1, 2, 4, 5, 3, 6, 7
        
        # 1. 定義 base case
        if not root:
            return None
        
        # 2. recursive call
        temp = root.left
        root.left = self.invertTree(root.right)
        root.right = self.invertTree(temp)
        return root

class Solution2:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        # iterative, BFS
        # time: O(N)
        # space: O(N), 最差情況是底層全部都有node，which is (N-1)/2
        #
        # for example:
        #     (1)
        #  (2)   (3)
        #(4)(5) (6)(7)
        #
        # queue的樣子依序是
        # 1
        # 2, 3
        # 3, 4, 5
        # 4, 5, 6, 7
        # (最後再一個個消掉，因為已經抵達最底層)
        from collections import deque  # a queue that can pop first item with O(1)
        q = deque()
        if root:
            q.append(root)
        while q:
            i = q.popleft()
            if i.left:
                q.append(i.left)
            if i.right:
                q.append(i.right)
            temp = i.left
            i.left = i.right
            i.right = temp
        return root

:::

<hr/>

<br>

## Live Coding

:::spoiler (name)

// write your code here

:::