“This is the sixth day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

Flip the binary tree

Good morning. Binary tree (heapSort) Binary tree (heapSort) Binary tree (heapSort) Binary tree This binary tree problem is simple, but it has a great history. It is said that Max Howell, the author of Homebrew, a popular software for the Mac, was rejected by Google for not being able to write a flipping binary tree algorithm on a whiteboard.

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t flip a binary tree on a whiteboard during an interview. That’s too bad.

So let’s take a look at the algorithm that Max Howell and Google missed out on.

Topic describes

Flip a binary tree. (Given the root of a binary tree, invert the tree, and return its root.)

Example 1:

Input:

4 / \ 27 / \ / \ 1 3 6 9Copy the code

Output:

4 / \ 7 2 / \ / 9 6 3 1Copy the code

Example 2:

Input: root =,2,7,1,3,6,9 [4] the Output:,7,2,9,6,3,1 [4]Copy the code

Ok, so that’s the general problem, and you can think about how to do that in five minutes. If you want to do the original problem you can go directly to the leetcode reference link at the end of this article.

Their thinking

When I see this flip problem, my intuition tells me to use recursion. If the left and right subtrees of the node root have been flipped, then we only need to switch the positions of the two subtrees to complete the flipping of the entire subtree with root as the root node.

In here, it is difficult to the understanding of the recursive function, the recursion is the concrete realization method of partition thought, using the call stack in the computer to realize the recursive content preservation, divided the whole problem into a a call stack, and then at the end of the call stack (recursive termination conditions) to solve (governance), thus to calculate the overall result is, step by step up.

Dynamic graph demonstration

Code implementation

var invertTree = function(root) {
  	// Return the node if the node is empty or a leaf node
    if(! root || ! root.left && ! root.right)return root; 
   	// Recursively, the left and right child nodes are flipped, and you can assume that the left and right child nodes have been flipped after executing the following code, which is the desired structure
    invertTree(root.left);
    invertTree(root.right);
  	// The child nodes of the root node have been swapped. Then the left and right children of the root node can be swapped
    let temp = root.left;
    root.left = root.right;
    root.right = temp;
    return root;
};
Copy the code

The iterative method implements the problem

In theory recursion and iteration can be converted to each other. Can readers solve this problem iteratively? That’s today’s quiz question. Readers are welcome to leave comments and feedback.

reference

226. Flip the binary tree