This is the 13th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

background

Learning the front end of three months, ready to brush interview questions, summary summary, a few interview questions a day, to the big factory.

In the last article, we have explained the basic knowledge of trees and binary trees: detail binary trees, calculate the depth of binary trees

Today we’re going to look at flipping binary trees, and there’s another interesting story:

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

Even the author of Homebrew can not learn, if we learn, isn’t NB Plus?

Problem: Flipping binary trees

parsing

Let’s use a graph to figure out what a flipped binary tree is. Flipped is left to right, not up to down.

Ideas:

We begin from the root node, recursive traversal of the tree, and the leaf node (the outermost leaf node) to exchange, and then the internal nodes (internal leaf node) to exchange, finally through to the root node (the root), only need to swap around two subtrees can complete the flip of the binary tree.

Let’s use GIF to demonstrate the effect (image from Likou):

code

    /** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */
    / * * *@param {TreeNode} root
     * @return {TreeNode}* /
    var invertTree = function(root) {
        if(root==null) return null;
        // Recursively flip the left side, essentially flipping from the outermost leaf node. Form the left subtree.
        var left=invertTree(root.left);
        // Recursively flip the right side, essentially starting from the outermost leaf node. Form the right subtree.
        var right=invertTree(root.right);
        // Swap left and right subtrees
        root.left=right;
        root.right=left;
        return root;
    };
Copy the code

Verification results:

Is it not so difficult to feel, understand the principle, or quite easy to implement.

conclusion

One step at a time, solid work!