Invert Binary Tree

refer to : https://www.algoexpert.io/questions/Invert%20Binary%20Tree

1. problem statement.

swap every left node in the tree for its corresponding right node.

2. 递归法（深度优先遍历）

O(n) time： we are traversing every single node

O(d) space: 需要存放

 1 import java.util.*;
 2 
 3 class Program {
 4   //O(n) time | O(d) space
 5   public static void invertBinaryTree(BinaryTree tree) {
 6         if(tree ==null){
 7             return;
 8         }
 9         swapHelper(tree);
10         invertBinaryTree(tree.left);
11         invertBinaryTree(tree.right);
12         
13   }
14     
15     public static void swapHelper(BinaryTree tree){
16         BinaryTree left = tree.left;
17         tree.left = tree.right;
18         tree.right = left;
19     }
20 
21   static class BinaryTree {
22     public int value;
23     public BinaryTree left;
24     public BinaryTree right;
25 
26     public BinaryTree(int value) {
27       this.value = value;
28     }
29   }
30 }

 1 def invertBinaryTree(tree):
 3     if tree is None:
 4         return
 5     swapHelper(tree)
 6     invertBinaryTree(tree.left)
 7     invertBinaryTree(tree.right)
 8     
 9 
10 def swapHelper(tree):
11     tree.left, tree.right = tree.right, tree.left
12 
13 
14 # This is the class of the input binary tree.
15 class BinaryTree:
16     def __init__(self, value):
17         self.value = value
18         self.left = None
19         self.right = None

3.迭代法（广度优先遍历, 队列）

O(n) time

O(n) space , 假设到了最后一层，我们把最后一层的所有孩子结点都加进队列中，for balanced tree, n/2 leaf nodes

initialize a queue
traverse level by level, root node-->next level
traverse the tree by using BFS manually
pop one node one time, get curr node
swap the curr.left and curr.right
add curr.left and curr.right into the queue
repeat 4-6 until queue is empty.

import java.util.*;

class Program {
    //O(n) time | O(n) space
  public static void invertBinaryTree(BinaryTree tree) {
        ArrayDeque<BinaryTree> queue = new ArrayDeque<BinaryTree>();
        //addLast() method to insert at end 
        queue.addLast(tree);
        while(queue.size() > 0){
            //removes the first element of the Deque and returns the same
            BinaryTree curr = queue.pollFirst();
            swapHelper(curr);
            if(curr.left != null){
                queue.addLast(curr.left);
            }
            if(curr.right != null){
                queue.addLast(curr.right);
            }
        }
  }
    
    public static void swapHelper(BinaryTree tree){
        BinaryTree left = tree.left;
        tree.left = tree.right;
        tree.right = left;
    }

  static class BinaryTree {
    public int value;
    public BinaryTree left;
    public BinaryTree right;

    public BinaryTree(int value) {
      this.value = value;
    }
  }
}

def invertBinaryTree(tree):
    queue = [tree]
    while len(queue):
        curr = queue.pop(0)
        if curr is None:
            continue
        swapHelper(curr)
        queue.append(curr.left)
        queue.append(curr.right)

def swapHelper(tree):
    tree.left, tree.right = tree.right, tree.left
# This is the class of the input binary tree.
class BinaryTree:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None