The profile

How basic is binary tree structure? 90% of our engineers use the software you wrote (Homebrew), But you can’t invert a binary tree on a whiteboard so f*** off. Further illustrates the importance of learning data structures and algorithms in order not to be despised by Google

Change the position of the two children in the binary tree, that is, left to right, right to left. You can’t use recursion.

The original problem

226. Invert Binary Tree (Easy)

Invert a binary tree.

Example:

Input:

Output:

Trivia: This problem was inspired by this original tweet by Max Howell:

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so f*** off.
Copy the code

226. Flipping binary trees (easy)

Flip a binary tree.

Example:

Input:

Output:

Note: This question was inspired by Max Howell’s original question:

Google: 90% of our engineers at Google use the software you wrote (Homebrew), but you can't flip binary trees on a whiteboard during an interview, which is... (You can't even flip a binary tree, what are you playing with?)Copy the code
  • Category: Tree

Analysis of the

If you understand the idea of recursion it’s easy to think of a way to solve a problem, and of course some of you might wonder, well, when do you know how to use recursion? Well, the easiest way to do that is if you have to iterate over and over and over again to get the result, you can always use recursion. The flip can essentially be split into two recursive steps, recursive flip of the left subtree and recursive flip of the right subtree. The idea is the same whether or not you use recursion, but using non-recursion requires the use of a stack or queue structure to store unswapped child nodes.

Concept design

Method 1: Loop, stack storage (DFS, non-recursive)

The basic idea is that the left and right nodes are swapped, the left and right children of each node are cyclically flipped, and the unflipped children are put on the stack until all the nodes in the stack are cyclically swapped. Pseudocode of method 1:

Method 2: Loop, queue storage (BFS, non-recursive)

The basic idea is that the left and right nodes are swapped, the left and right children of each node are rotated, and the unflipped children are queued until all the nodes in the stack are swapped.

  • Pseudocode of method 1 and Method 2:
1, check whether the root node is null, if null, return NULL; 2. Create a stack (queue) for node storage and initially store the root node to the stack (queue); 3,whileLoop, end loop when stack (queue) is empty; I. Push (queue) a node and interact the left and right child nodes of the node; Ii. Check whether the left and right child nodes are null. If not, continue to push the left and right nodes to the stack (queue). 4. The loop switch ends and the root node is returned.Copy the code

Method three: recursion

The basic idea is that the left and right nodes are exchanged, and the recursive call before the exchange processes the left and right nodes of the root node respectively to ensure that the left and right nodes have been flipped before the exchange.

  • Method 3 pseudocode:
1, check whether the root node is null, if null, return NULL; 2. Switch the left and right nodes of the node; 3. Recursive interaction between left and right subtrees;Copy the code

Coding practices

The stack to achieve

	   public TreeNode invertTree(TreeNode root) {	        
	        if (root == null) {
	            return null;
	        }
	        Stack<TreeNode> stack = new Stack<>();
	        stack.push(root);	        
	        while(! stack.isEmpty()) { final TreeNode node = stack.pop(); final TreeNode left = node.left; node.left = node.right; node.right = left;if(node.left ! = null) { stack.push(node.left); }if(node.right != null) {
	                stack.push(node.right);
	            }
	        }
	        return root;
	    }
Copy the code

Queue implementation

	public TreeNode invertTree(TreeNode root) {
		if (root == null) {
			return null;
		}
		Queue<TreeNode> queue = new LinkedList<>();
		queue.offer(root);
		while(! queue.isEmpty()) { TreeNode node = queue.poll(); TreeNode left = node.left; node.left = node.right; node.right = left;if(node.left ! = null) { queue.offer(node.left); }if (node.right != null) {
				queue.offer(node.right);
			}
		}
		return root;
	}
Copy the code

The recursive implementation

	public TreeNode invertTree(TreeNode node) {
		if (node == null) {
			return null;
		}
		TreeNode temp = node.left;
		node.left = node.right;
		node.right = temp;
		invertTree(node.left);
		invertTree(node.right);
		return node;
	}
Copy the code

eggs

Comparing the execution results of the three implementation codes, it can be found that the efficiency of leetcode evaluation of the three methods is 100%, but the runtime time of method 1 is 1ms, while the runtime time of method 2 and method 3 is 0ms. Why is it slower to use Stack than LinkedList for the same algorithmic idea with a different data structure? That’s the Easter egg!

conclusion

Binary tree flipping using non-recursive implementation is a basic knowledge of the question, the binary tree flipping using non-recursive implementation of DFS and BFS, finally if you think it is useful, give a like 0.0 ~