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: 需要存放 O(d) 个函数调用(d是树的深度)
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
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