Sword finger offer | interview question 21: mirror image of binary tree

Knock algorithm series articles

"Leetcode : https://leetcode-cn.com/problems/er-cha-shu-de-jing-xiang-lcof

"GitHub : https://github.com/nateshao/leetcode/blob/main/algo-notes/src/main/java/com/nateshao/sword_offer/topic_21_mirrorTree/Solution.java

Sword finger Offer 20 Image of binary tree

Please complete a function, input a binary tree, and the function outputs its image.

For example, enter:

        4
      /   \
     2     7
    / \   / \
   1   3 6   9

Mirror output:

        4
      /   \
     7     2
   / \   / \
  9   6 3   1

Example 1:

Input: root = [4,2,7,1,3,6,9]
Output:[4,7,2,9,6,3,1]

Limit: 0 < = number of nodes < = 1000

analysis

Binary tree image definition: for any node root in the binary tree, set its left / right child nodes as left and right respectively; The left / right child nodes of the corresponding root node in the binary tree image are right and left respectively.

Method 1: recursive method

According to the definition of binary tree image, considering the recursive traversal (dfs) of binary tree, the left / right child nodes of each node can be exchanged to generate the image of binary tree.

Recursive parsing:

Termination condition: when the node root is empty (i.e. crossing the leaf node), null is returned;
Recursive work:
1. Initialize node tmp to temporarily store the left child node of root
2. Turn on the recursive right child node mirrorTree(root.right), and take the return value as the left child node of root.
3. Turn on the recursive left child node mirrorTree(tmp) and take the return value as the right child node of root.
Return value: returns the current node root;

"Q: why do you need to temporarily store the left child node of root? A: after the recursive right child node" root.left = mirrorTree(root.right); "after execution, the value of root.left has changed. At this time, the recursive left child node mirrorTree(root.left) will have problems.

Complexity analysis:

Time complexity 0(N): where N is the number of nodes of the binary tree. To establish a binary tree image, you need to traverse all nodes of the tree, taking O(N) time.
Space complexity O(N): in the worst case (when the binary tree degenerates into a linked list), the system needs to use stack space of O(N) size for recursion.

package com.nateshao.sword_offer.topic_21_mirrorTree;

import java.util.Stack;

/**
 * @date Created by Shao Tongjie on 2021/11/24 22:48
 * @WeChat official account programmers
 * @Personal website www.nateshao.com cn
 * @Blog https://nateshao.gitee.io
 * @GitHub https://github.com/nateshao
 * @Gitee https://gitee.com/nateshao
 * Description: Sword finger Offer 27 Image of binary tree
 */
public class Solution {
    /**
     * recursion
     *
     * @param root
     * @return
     */
    public TreeNode mirrorTree(TreeNode root) {
        if (root == null) return null;
        TreeNode node = root.left;
        root.left = mirrorTree(root.right);
        root.right = mirrorTree(node);
        return root;
    }

    /**
     * Solution 1: recursion, time complexity: O(n), space complexity: O(n)
     *
     * @param root
     * @return
     */
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return isMirror(root.left, root.right);
    }

    private boolean isMirror(TreeNode leftNode, TreeNode rightNode) {
        if (leftNode == null && rightNode == null) return true;
        if (leftNode == null || rightNode == null) return false;

        return leftNode.val == rightNode.val && isMirror(leftNode.left, rightNode.right) && isMirror(leftNode.right, rightNode.left);
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

}

Method 2: auxiliary stack (or queue)

Use the stack (or queue) to traverse all nodes of the tree and exchange the left / right child nodes of each node.

Algorithm flow:

Special case handling: when root is empty, null is returned directly;
Initialization: stack (or queue). This paper uses the stack and adds the root node root.
Loop switching: jump out when stack is controlled;
1. Out of stack: recorded as node;
2. Add child node: stack the left and right child nodes of node;
3. Swap: swap the left 1 and right child nodes of node.
Return value: returns the root node.

Complexity analysis:

Time complexity 0(N): where N is the number of nodes of the binary tree. To establish a binary tree image, you need to traverse all nodes of the tree, taking O(N) time.
Space complexity O(N): as shown in the figure below, in the worst case, the stack can store N+1/2 nodes at most at the same time, occupying O(N) additional space.

package com.nateshao.sword_offer.topic_21_mirrorTree;

import java.util.Stack;

/**
 * @date Created by Shao Tongjie on 2021/11/24 22:48
 * @WeChat official account programmers
 * @Personal website www.nateshao.com cn
 * @Blog https://nateshao.gitee.io
 * @GitHub https://github.com/nateshao
 * @Gitee https://gitee.com/nateshao
 * Description: Sword finger Offer 27 Image of binary tree
 */
public class Solution {
    /**
     * Stack
     *
     * @param root
     * @return
     */
    public TreeNode mirrorTree1(TreeNode root) {
        if (root == null) return null;
        Stack<TreeNode> stack = new Stack<TreeNode>() {{
            add(root);
        }};
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (node.left != null) stack.add(node.left);
            if (node.right != null) stack.add(node.right);
            TreeNode tmp = node.left;
            node.left = node.right;
            node.right = tmp;
        }
        return root;
    }
    /**
     * Solution 2: iteration, time complexity: O(n), space complexity: O(n)
     *
     * @param root
     * @return
     */
    public boolean isSymmetric2(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode t1 = stack.pop();
            TreeNode t2 = stack.pop();
            if (t1 == null && t2 == null) continue;
            if (t1 == null || t2 == null) return false;
            if (t1.val != t2.val) return false;

            stack.push(t1.left);
            stack.push(t2.right);
            stack.push(t1.right);
            stack.push(t2.left);
        }
        return true;
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

}

Reference link: https://leetcode-cn.com/problems/er-cha-shu-de-jing-xiang-lcof/solution/mian-shi-ti-27-er-cha-shu-de-jing-xiang-di-gui-fu-

The revolution has not yet succeeded, and comrades still need to work hard and rush

Added by HektoR on Thu, 30 Dec 2021 02:41:30 +0200

Programming VIP