【题27 二叉树的镜像】

╰+攻爆jí腚メ 2022-03-25 13:20 256阅读 0赞

**【题27 二叉树的镜像】**  
**【题目】**  
请完成一个函数，输入一棵二叉树，该函数输出它的镜像。  
**镜像：**  
![在这里插入图片描述][20190121102544912.png]  
**特点：**  
两棵树的根节点相同，但它们的左右两个子节点交换了位置，因此，不妨先在树中交换根节点的两个子节点。  
交换根节点的2个子节点之后，注意到10，6的节点的子节点仍然保持不变，还需要交换这两个节点的左右子节点。做完这两次交换之后，已经遍历完所有的非叶节点，此时交换之后的树，刚好就是原始树的镜像。  
![在这里插入图片描述][20190121102554676.png]  
**总结过程：**  
先前序遍历这棵树的每个节点，如果遍历到的节点有子节点，就交换它的2个子节点，当交换完所有非叶节点的左右子节点之后，就得到了树的镜像。

**实现**

/**
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    
        public TreeNode(int val) {
            this.val = val;
    
        }
    
    }
    */
    public class Solution {
        public void Mirror(TreeNode root) {
            TreeNode temp; //创建中间节点
            if(root != null){//如果根节点不为空，交换节点
                temp = root.left;
                root.left = root.right;
                root.right = temp;
                if(root.left != null){//如果根节点的左子树不为空，递归
                    Mirror(root.left);
                }
                if(root.right != null){//如果根节点的右子树不为空，递归
                    Mirror(root.right);
                }
            }
        }
    }

[20190121102544912.png]: /images/20220325/6f1849f9dc7b4ff1aa5c2fb0de4e5528.png
[20190121102554676.png]: /images/20220325/09f1af288ec44b5f9c54d0a3fbf3850b.png