剑指 Offer 27. 二叉树的镜像

一时失言乱红尘 2022-09-10 04:23 70阅读 0赞

> 请完成一个函数，输入一个二叉树，该函数输出它的镜像。
> 
> 例如输入：
> 
> 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\]  
> 
> 
> 限制：
> 
> 0 <= 节点个数 <= 1000
> 
> 来源：力扣（LeetCode）  
> 链接：https://leetcode-cn.com/problems/er-cha-shu-de-jing-xiang-lcof  
> 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

第一种方法：这种方法类似于 bfs 广度优先搜索

// 这种方法类似于 bfs 广度优先搜索
    // 先把左右节点入栈，然后再交换
    class Solution {
        public TreeNode mirrorTree(TreeNode root) {
            if(root == null)return null;
            Stack<TreeNode> stack = new Stack<>();
            stack.add(root);
            while(!stack.isEmpty()){
                TreeNode treeNode = stack.pop();
                if(treeNode.left != null)stack.add(treeNode.left);
                if(treeNode.right != null)stack.add(treeNode.right);
                TreeNode tmp = treeNode.left;
                treeNode.left = treeNode.right;
                treeNode.right = tmp;
            }
            return root;
        }
    }

第二种方法：类似于 dfs 深度优先搜索，递归

public TreeNode mirrorTree(TreeNode root){
            // 先判断是否为null，如果为null则直接返回
            if(root == null)return null;
            // 如果不为null，则递归进行交换
            TreeNode right = mirrorTree(root.right);
            TreeNode left = mirrorTree(root.left);
    
            TreeNode tmp = left;
            root.left = right;
            root.right = tmp;
            return root;
        }

--------------------

主动思考 和 知识再加工，是记忆的底层逻辑，因为大脑不擅长记忆无意义的东西。

大脑能记住的，是“我们仔细思考过的东西”。（美 威林厄姆《学生为什么不喜欢上学》）

精细化提问，可以显著提高被试的学习和保持效果。（美 苏珊·A·安布罗斯《聪明教学 7 原理》）