Hello, everyone, I am the beaten Amumu, love algorithm front-end fish old. Recently, I will frequently share with you my thoughts and experiences in the process of brush algorithm. If you also want to improve the forced case of fish old, welcome to pay attention to me, learn together.

The title

226. Flip the binary tree

Flip a binary tree.

Example:

Input:

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

Output:

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

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

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.

Train of thought

  1. This topic before we use recursive solution once, if you have not seen the small partners can take a look at my article [Luffy]_ front-end developers binary tree introduction tutorial;
  2. Main share how to use iterative method to do today, the topic of binary tree, the normal binary tree with recursive solution is the fastest, but recursion too deep to bring the side effects of stack overflow, for example we have a Map object, iterative method only needs to be defined in function, can be used, and the recursive method need to keep it as a parameter to pass down layers;
  3. The essence of iteration is to find the secret of transforming the current round into the next round. For example, the iteration of a tree can move from the current layer to the next layer and then step by step.
  4. So we just need to collect the effective nodes of the next round, and iterate the next round’s value as the current value after the current round is executed.

implementation

/** * 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) {
    // The stack and queue are the same, one is DFS and the other is BFS
    let queue = [ root ];

    // If there is another round
    while (queue.length) {
        // Execute the current round, and then take the valid node of the next round as the current value for the next round
        queue = queue.reduce((total, cur) = > {
            if(! cur)return total;
            // Switch the positions of the left and right nodes
            [ cur.right, cur.left ] = [ cur.left, cur.right ]

            // Record the valid nodes of the round
            cur.left && total.push(cur.left);
            cur.right && total.push(cur.right);
            returntotal; } []); }return root;
};
Copy the code

If you understand it, you can click on it and see you in the next topic. If there is no accident after the article will be in this form, there are good suggestions welcome to comment area.