【剑指offer】面试题27：二叉树的镜像

我不是女神ヾ 2022-04-10 13:15 158阅读 0赞

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

牛客网题目链接：[https://www.nowcoder.com/questionTerminal/564f4c26aa584921bc75623e48ca3011][https_www.nowcoder.com_questionTerminal_564f4c26aa584921bc75623e48ca3011]

如下图所示：两棵互为镜像的二叉树：

![20190107144333828.png][]

仔细分析这两棵树的特点，看看能不能总结出求镜像的步骤。这两棵树的根节点相同，但它们的左右两个子节点交换了位置。因此我们不妨先在树中交换根节点的两个子节点，就得到了下面的第二颗树：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70][]

交换根节点的两个子节点之后，我们注意到值为10，6的结点的子节点仍然保持不变，因此我们还需要交换这两个结点的左右子节点。交换之后的结果分别为第三课树和第四颗树。做完这两次交换之后，我们已经遍历完所有的非叶子结点。此时交换之后的树刚好就是原始树的镜像。

总结上面的过程，我们得出求一棵树的镜像的过程：**我们先前序遍历这棵树的每个结点，如果遍历的结点有子节点，就交换它的两个子节点，当交换完所有的非叶子结点的左右子节点之后，我们就得到了树的镜像。**

public class MirrorTree {
    
    	class TreeNode{
    		private int val = 0;
    		private TreeNode left = null;
    		private TreeNode right = null;
    		
    		public TreeNode(int val){
    			this.val = val;
    		}
    	}
    	
    	public void mirror(TreeNode root){
    		if(root == null){
    			return;
    		}
    		// 只有一个节点时，即：只有根节点
    		if(root.left == null && root.right == null){
    			return;
    		}
    		
    		// 交换当前节点的左右子节点
    		TreeNode temp = root.left;
    		root.left = root.right;
    		root.right = temp;
    		
    		// 左子树递归
    		if(root.left != null){
    			mirror(root.left);
    		}
    		
    		// 右子树递归
    		if(root.right != null){
    			mirror(root.right);
    		}
    	}
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 1][]

![20190107151829705.png][]

public class MirrorTree {
    
    	class TreeNode{
    		private int val = 0;
    		private TreeNode left = null;
    		private TreeNode right = null;
    		
    		public TreeNode(int val){
    			this.val = val;
    		}
    	}
    	
    	/**
    	 * 非递归方法
    	 */
    	public void mirror2(TreeNode root){
    		if(root == null){
    			return;
    		}
    		
    		Stack<TreeNode> stack = new Stack<TreeNode>();
    		stack.push(root);
    		while(!stack.isEmpty()){
    			TreeNode node = stack.pop();
    			if(node.left != null || node.right != null){
    				TreeNode temp = node.left;
    				node.left = node.right;
    				node.right = temp;
    			}
    			if(node.left != null){
    				stack.push(node.left);
    			}
    			if(node.right != null){
    				stack.push(root.right);
    			}
    		}
    	}
    }

[https_www.nowcoder.com_questionTerminal_564f4c26aa584921bc75623e48ca3011]: https://www.nowcoder.com/questionTerminal/564f4c26aa584921bc75623e48ca3011
[20190107144333828.png]: /images/20220330/805e2ae099a845a3ba97a3d211f6c872.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70]: /images/20220330/98f33383a3514642832782ba01ae1d22.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 1]: /images/20220330/312e718c473c47c880e742725ecf5577.png
[20190107151829705.png]: /images/20220330/920c2aecc1b9454fa316fe2a45013153.png