The article directories

        • Problem description
        • Solution 1: Recursion (pre-traversal + post-traversal)
        • Solution 2: Uniform writing iterative method (pre-order traversal + post-order traversal)
        • Solution 3: Sequence traversal

Problem description

Flip a binary tree.

Example:

Input:

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

Output:

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

Solution 1: Recursion (pre-traversal + post-traversal)

Let’s look at the recursion trilogy:

Determine the arguments and return values of the recursive function

Parameters are Pointers to nodes that need to be passed in. No other parameters are needed. The main parameters are usually set at this time, and if additional parameters are found in writing recursive logic, they can be added at any time.

Return TreeNode*; TreeNode*; TreeNode*; TreeNode*

TreeNode invertTree(TreeNode root)
Copy the code

Determine termination conditions

Returns when the current node is empty

  if(root==null) return null;
Copy the code

Determine the logic of a single layer recursion

Because it is pre-ordered traversal, we swap the left and right child nodes first, then reverse the left subtree, and reverse the right subtree.

   TreeNode temp = root.left;
   root.left = root.right;
   root.right=temp;
   invertTree(root.left);
   invertTree(root.right);
Copy the code

Based on this recursive three-step method, the code is basically finished, the code is as follows (preorder) :

class Solution {
    public TreeNode invertTree(TreeNode root) {
       if(root==null) returnnull; TreeNode temp = root.left; Root. left = root.right; root.right=temp; invertTree(root.left); invertTree(root.right);returnroot; }}Copy the code

Recursion includes pre-order, middle-order and post-order. Pre-order or post-order can be used when flipping binary trees, but middle-order cannot be used. The post-order code is as follows:

class Solution {
    public TreeNode invertTree(TreeNode root) {
       if(root==null) return null;
       invertTree(root.left);
       invertTree(root.right);
       TreeNode temp = root.left;
       root.left = root.right;
       root.right=temp;
       returnroot; // Return the root of the binary tree, so the recursion cannot accept the return value, as long as it does not receive, the recursive return value is invalid}}Copy the code

Solution 2: Uniform writing iterative method (pre-order traversal + post-order traversal)

Whiteboard interviews require code to be written correctly, so iteration is as long as you learn the deepest understanding of it

The preceding sequence traversal, the code is as follows:

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root==null) return null;
        Stack<TreeNode> stack=new Stack<TreeNode>();
        stack.push(root);
        while(! stack.isEmpty()){ TreeNode node=stack.peek(); // The top oneif(node ! = null){ stack.pop();if(node.right! =null) stack.push(node.right);if(node.left! =null) stack.push(node.left); stack.push(node); stack.push(null); }else{ stack.pop(); node=stack.pop(); TreeNode temp = node.left; node.left = node.right; node.right=temp; }}returnroot; // Finally return the root node}}Copy the code

Post-order traversal – unified writing, as follows:

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root==null) returnnull; // Stack. Push is not requiredif(null ! If root is null, null Stack<TreeNode> Stack =new Stack<TreeNode>(); stack.push(root);while(! stack.isEmpty()){ TreeNode node=stack.peek(); // The top one is not a popupif(node ! = null){ stack.pop(); stack.push(node); stack.push(null);if(node.right! =null) stack.push(node.right);if(node.left! =null) stack.push(node.left); }else{ stack.pop(); node=stack.pop(); TreeNode temp = node.left; node.left = node.right; node.right=temp; }}returnroot; }}Copy the code

Solution 3: Sequence traversal

Level traversal can also flip the tree, because the level traversal can also flip the left and right children of each node as follows:

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root==null) returnnull; Queue<TreeNode> queue=new LinkedList<>(); queue.offer(root); // Insert the root node, i.e. insert the first nodewhile(! queue.isEmpty()){ int size=queue.size();for(int i=0; i<size; i++) { TreeNode node = queue.poll(); // TreeNode temp = node.left; node.left = node.right; node.right = temp; invertTree(root.left); invertTree(root.right); }}returnroot; }}Copy the code