TechNomads

题目

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

例如输入：

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

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

解法-递归

go代码实现如下：

func mirrorTree(root *TreeNode) *TreeNode {
    if root == nil {
        return root;
    }

    var node = mirrorTree(root.Left)
    root.Left = mirrorTree(root.Right)
    root.Right = node

    return root
}

解法-非递归（栈）

辅助栈（或队列）
利用栈（或队列）遍历树的所有节点 nodenode ，并交换每个 nodenode 的左 / 右子节点。

算法流程：

• 特例处理： 当 rootroot 为空时，直接返回null ；
• 初始化： 栈（或队列），本文用栈，并加入根节点 root 。
• 循环交换： 当栈 stack 为空时跳出；
• 出栈： 记为 node ；
• 添加子节点： 将 node 左和右子节点入栈；
• 交换： 交换 node 的左 / 右子节点。
• 返回值： 返回根节点 root 。

public TreeNode mirrorTree(TreeNode root) {
        if(root == null) return null;
        Stack<TreeNode> stack = new 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;
    }