当前位置：网站首页>Sword finger offer 27 Image of binary tree

Sword finger offer 27 Image of binary tree

2022-07-07 22:52:00 【Yes' level training strategy】

subject ： Please complete a function , Enter a binary tree , This function outputs its image .

For example, the input ：

airplay mirroring ：

Example 1：

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

Output ：[4,7,2,9,6,3,1]

The subject is not difficult to understand , Recursively exchange two positions , The most direct idea is to use recursion ：

The code is as follows ：

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution {
    
    public TreeNode mirrorTree(TreeNode root) {
    
        if (root == null) {
    
            return null;
        }
        TreeNode left = mirrorTree(root.left);
        TreeNode right = mirrorTree(root.right);
        root.left = right;
        root.right = left;
        return root;
    }
}

Time complexity ：O(n)

Spatial complexity ：O(n)

It should be possible to do recursion after a few times , So this is also a simple problem .

Of course, recursion can be realized by stack , So let's take a look at the code implementation of the auxiliary stack ：

class Solution {
    
    public TreeNode mirrorTree(TreeNode root) {
    
        if (root == null) {
    
            return null;
        }
        Deque<TreeNode> nodeStack = new ArrayDeque(); // stack  Recommend to use Deque
        nodeStack.add(root);
        while (!nodeStack.isEmpty()) {
    
            TreeNode node = nodeStack.removeLast();
            if (node.right != null) {
    
                nodeStack.add(node.right);
            }
            if (node.left != null) {
    
                nodeStack.add(node.left);
            }
            TreeNode tempNode = node.left;
            node.left = node.right;
            node.right = tempNode;
        }
        return root;
    }
}