The title
!!!!! Flip binary tree – force buckle
Analysis of the
We can see from the example that the so-called flipping of a binary tree is to swap the left and right nodes of each binary tree.
Here we use the GIF in the solution of LeetCode to illustrate the problem:
So the whole idea is simple:
- The first step of the recursion, of course, is to find the boundary: the boundary here is naturally null by the node
- The left and right nodes are swapped
- Recursively traverses the left and right nodes
So implement the code as follows:
var invertTree = function (root) {
if (root === null) {
return root;
}
let temp = root.left;
root.left = root.right;
root.right = temp;
invertTree(root.left);
invertTree(root.right);
return root;
};
Copy the codeThe results are as follows:
!!!!! 💡 Tip: Some readers here may be confused. Wouldn’t there be chaos if the left and right nodes were swapped?
In fact, the GIF of the algorithm may have a misleading effect on the above questions. In fact, after the left and right nodes are swapped, the tree should be as follows:
In fact, after the nodes are flipped, their Pointers to their children remain the same, so this can be done.
To optimize the
We use a temporary variable, which in Javascript can be dispensed with entirely, using the same trick we mentioned earlier: destruct assignment:
var invertTree = function (root) {
if (root === null) return root;
[root.left, root.right] = [invertTree(root.right), invertTree(root.left)];
return root;
};
Copy the codeThe results are as follows:
It’s in the back
Max Howell, author of Homebrew, was rejected for an interview at Google because he couldn’t write a flipped binary tree. When he got home, he couldn’t figure it out, so he joked about it on Twitter: So many people in your company use the software I wrote, but because I can’t write the flip binary tree to brush me off, simply * 🐕.