jz27.二叉树的镜像

题目描述

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

例如输入：

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

镜像输出：

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

示例一：

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

题解

递归方法

在解题之前要先了解 二叉树的镜像 是什么:

二叉树镜像定义： 对于二叉树中任意节点root ，设其左 / 右子节点分别为 left, right ；则在二叉树的镜像中的对应root节点，其左 / 右子节点分别为 right, left。

递归的思路很简单, 就是遍历每个节点, 交换其左右子树即可

1. 终止条件: 当节点root 为空时, 返回null
2. 递归过程:
   1. 初始化一个临时节点temp 暂存 左儿子
   2. 令左儿子等于右儿子
   3. 令右儿子等于临时节点
3. *返回值: *当前的节点root

public class jz27 {
    public TreeNode mirrorTree(TreeNode root) {
        return recur(root);
    }

    private TreeNode recur(TreeNode root) {
        if (root==null) return null;
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        recur(root.left);
        recur(root.right);
        return root;
    }
}

---

栈遍历方法

利用栈或队列遍历树的所有节点, 交换每个节点的左右儿子

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 temp = node.left;
            node.left = node.right;
            node.right = temp;
        }
        return root;
    }