Topic describes

Flip a binary tree. Example: Input: 4 / \ 27 / \ / \ 13 6 9 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.

Source: LeetCode link: leetcode-cn.com/problems/in… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

A bigwig joked that he was rejected for an interview with Google because he didn’t write a flipped binary tree

Knowledge review:

Pre-order, mid-order, post-order traversal concept

Using the root node as a reference:

  • DLR– Forward traversal (root first, left to right, root of a tree always in front of left subtree, left subtree always in front of right subtree)

  • LDR- Middle order traversal (root in middle, left to right, left subtree of a tree always in front of root, root always in front of right subtree)

  • LRD– Backward traversal (root behind, left to right, left subtree of a tree always in front of right subtree, right subtree always in front of root)

Their thinking

Idea 1: Breadth-first traversal of BFS

  • Using the principle of first in, first out (FIFO) of queue, element exchange is carried out.
  • Initialize the queue: queue=[root]
  • Extract the element that joins the queue first;
    • If the current node is null, the next node is traversed.
    • Otherwise, swap left and right subtrees;
    • End of the exchange, from left to right continue to join the team;
  • Breadth-first traversal is completed, so the current tree completes all interactive flips;

code

/** * Definition for a binary tree node. * class TreeNode { * val: number * left: TreeNode | null * right: TreeNode | null * constructor(val? : number, left? : TreeNode | null, right? : TreeNode | null) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } * } */

function invertTree(root: TreeNode | null) :TreeNode | null {
    // Idea 1: breadth-first traversal: use the first-in, first-out principle of queues to swap elements;
    let queue=[root]; // Initialize the queue;
     while(queue.length>0) {// Retrieve the element that joins the queue first;
         let current =queue.shift();
          if(current===null) {continue;
          }
          // If the current node exists, the left and right subtrees are swapped;
          [current.left,current.right]=[current.right,current.left]
          // Start from left to right;
          queue.push(current.left);
          queue.push(current.right)
     }// end of queue until all elements are breadth-first traversed;
    return root;

};
Copy the code

Idea 2: Use the stack feature

  • In the same way as above
    • You can use the stack stack data structure of the first in last out principle;
function invertTree(root: TreeNode | null) :TreeNode | null {
    // The same can be used to stack the data structure of the first in last out principle;
     let stack=[root]
     while(stack.length>0) {let current=stack.pop();
         if(current===null) {continue;
         }
         // Switch left and right subtree nodes;
         [current.left,current.right]=[current.right,current.left]
         // Stack first out principle,
         stack.push(current.right);
         stack.push(current.left);
     }// end of stack
    return root;
};
Copy the code

Idea 3: Depth-first traversal of DFS

Recursion: fore-order traversal

  • Sequential traversal:
    • Process the root element first, then the left subtree, then the right subtree;
function invertTree(root: TreeNode | null) :TreeNode | null {
  // The root element is processed first, then the left subtree, then the right subtree;
  if(root===null) {return root;
  }
  // Interoperate with the element
  [root.left,root.right]=[root.right,root.left]
  // Process the left subtree;
   invertTree(root.left);
   // Process the right subtree
   invertTree(root.right);
   return root;
  
};

Copy the code
  • Post-order traversal:
    • We’ll do the left subtree, and then we’ll do the right subtree; Finally, with the root element,
function invertTree(root: TreeNode | null) :TreeNode | null {
  // The root element is processed first, then the left subtree, then the right subtree;
  if(root===null) {return root;
  }

   // Process the left subtree;
   invertTree(root.left);
   // Process the right subtree
   invertTree(root.right);

  // Interoperate with the element
  [root.left,root.right]=[root.right,root.left]
   return root;
  
};
Copy the code

A review of binary trees

【 Review old and learn new 】101. Symmetric binary treesUsing queue, recursive realization of binary tree judgment

【 Review old and learn new 】102. Sequence traversal of binary treesBreadth-first traversal, queue first in, first out principle

【 Review old and learn new 】104. Maximum depth of a binary treeBreadth-first traversal, recursive implementation

【 Review old and learn new 】1367. Lists in binary treesRecursive decomposition problem solving