剑指 Offer 27. 二叉树的镜像

in with 0 comment

剑指 Offer 27. 二叉树的镜像

请完成一个函数,输入一个二叉树,该函数输出它的镜像。

例如输入:

     4    /  
  2     7  / \   /
1   3 6   9 镜像输出:

     4    /  
  7     2  / \   /
9   6 3   1

示例 1:

输入:root = [4,2,7,1,3,6,9]
输出:[4,7,2,9,6,3,1]

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/er-cha-shu-de-jing-xiang-lcof 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路

  1. 递归,申明 tmp 做临时 node,交换左右节点,直到节点为 null 退出递归,返回 root
  2. 栈,将根节点压入栈中,开始遍历树,当栈不为空时,先出栈,判断该节点的左右节点是否为 null,如果不将节点压入栈中,并将当前节点的左右节点调换位置。直到栈为空,遍历完整个二叉树并交换左右子树。

代码

解法一

/**
 * 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 tmp = root.left;
        root.left = mirrorTree(root.right);
        root.right = mirrorTree(tmp);
        return root;
    }
}

解法二

/**
 * 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;
        Stack<TreeNode> stack = new Stack<>();
        stack.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;
    }
}