Nuggets team number online, help you Offer impromptu! Click on theCheck the details

1. Title Description

Complete a function that inputs a binary tree and outputs its mirror image.

Example:

The existing matrix matrix is as follows:

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

Mirror output:

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

Example of program output:

Input: root = [4,2,7,1,3,6,9]Copy the code

Limitations:

0 <= Number of nodes <= 1000Copy the code

Second, train of thought analysis

My train of thought

Swap the left and right subtrees of root, and then recursively swap the left and right subtrees. The main thing to notice is that if the left subtree is empty, or if the right subtree is empty, you don’t recurse, you recurse only on the branch end.

The best way of thinking

The idea of solving the problem is roughly the same as what I have considered. Another way is to use the stack to solve the problem, because it is recursive in nature, so the idea of using the stack is the same.

AC code

public TreeNode mirrorTree(TreeNode root) {
    // Consider the boundary conditions first
  	if (root == null || root.right == null && root.left == null) {
        return root;
    }
  	// Do a swap from the root
    TreeNode tmp = root.left;
    root.left = root.right;
    root.right = tmp;
  	// If the right or left subtrees are not empty, then a new tree can be considered and continue to swap their left and right subtrees
    if(root.right ! =null) {
        mirrorTree(root.right);
    }
    if(root.left ! =null) {
        mirrorTree(root.left);
    }
    return root;
}
Copy the code

Four,

A very simple problem, as long as you understand the recursion idea, and grasp some boundary cases should not be a problem, the solution idea is relatively unique.