434,剑指 Offer

The more you know who you are and what you want, the less you let things upset you.

你越了解自己以及自己想要的东西,你就越不会被外界困扰。

问题描述

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

例如输入:

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

BFS解决

之前讲373,数据结构-6,树的时候,提到过二叉树的广度优先搜索,就是一层一层的访问,像下面这样

二叉树的BFS代码如下

 1public static void treeBFS(TreeNode root) { 2    //如果为空直接返回 3    if (root == null) 4        return; 5    //队列 6    Queue<TreeNode> queue = new LinkedList<>(); 7    //首先把根节点加入到队列中 8    queue.add(root); 9    //如果队列不为空就继续循环10    while (!queue.isEmpty()) {11        //poll方法相当于移除队列头部的元素12        TreeNode node = queue.poll();13        //打印当前节点14        System.out.println(node.val);15        //如果当前节点的左子树不为空,就把左子树16        //节点加入到队列中17        if (node.left != null)18            queue.add(node.left);19        //如果当前节点的右子树不为空,就把右子树20        //节点加入到队列中21        if (node.right != null)22            queue.add(node.right);23    }24}

这题要求的是输出二叉树的镜像,就是每一个节点的左右子节点进行交换,随便画个二叉树看一下

我们需要遍历每一个节点,然后交换他的两个子节点,一直循环下去,直到所有的节点都遍历完为止,代码如下

 1public TreeNode mirrorTree(TreeNode root) { 2    //如果为空直接返回 3    if (root == null) 4        return null; 5    //队列 6    final Queue<TreeNode> queue = new LinkedList<>(); 7    //首先把根节点加入到队列中 8    queue.add(root); 9    while (!queue.isEmpty()) {10        //poll方法相当于移除队列头部的元素11        TreeNode node = queue.poll();12        //交换node节点的两个子节点13        TreeNode left = node.left;14        node.left = node.right;15        node.right = left;16        //如果当前节点的左子树不为空,就把左子树17        //节点加入到队列中18        if (node.left != null) {19            queue.add(node.left);20        }21        //如果当前节点的右子树不为空,就把右子树22        //节点加入到队列中23        if (node.right != null) {24            queue.add(node.right);25        }26    }27    return root;28}

DFS解决

无论是BFS还是DFS都会访问到每一个节点,访问每个节点的时候交换他的左右子节点,直到所有的节点都访问完为止,代码如下

 1public TreeNode mirrorTree(TreeNode root) {//DFS 2    //如果为空直接返回 3    if (root == null) 4        return null; 5    //栈 6    Stack<TreeNode> stack = new Stack<>(); 7    //根节点压栈 8    stack.push(root); 9    //如果栈不为空就继续循环10    while (!stack.empty()) {11        //出栈12        TreeNode node = stack.pop();13        //子节点交换14        TreeNode temp = node.left;15        node.left = node.right;16        node.right = temp;17        //左子节点不为空入栈18        if (node.left != null)19            stack.push(node.left);20        //右子节点不为空入栈21        if (node.right != null)22            stack.push(node.right);23    }24    return root;25}

中序遍历解决

这题其实解法比较多,只要访问他的每一个节点,然后交换子节点即可,我们知道二叉树不光有BFS和DFS访问顺序,而且还有前序遍历,中序遍历和后续遍历等,不管哪种访问方式,只要能把所有节点都能访问一遍然后交换子节点就能解决,我们这里就以中序遍历来看下,前序和后序就不在看了。在373,数据结构-6,树中,提到二叉树中序遍历的非递归写法如下

 1public static void inOrderTraversal(TreeNode tree) { 2    Stack<TreeNode> stack = new Stack<>(); 3    while (tree != null || !stack.isEmpty()) { 4        while (tree != null) { 5            stack.push(tree); 6            tree = tree.left; 7        } 8        if (!stack.isEmpty()) { 9            tree = stack.pop();10            System.out.println(tree.val);11            tree = tree.right;12        }13    }14}

我们来对他改造一下,就是在访问每个节点的时候交换,代码如下

 1public static TreeNode mirrorTree(TreeNode root) { 2    //如果为空直接返回 3    if (root == null) 4        return null; 5    Stack<TreeNode> stack = new Stack<>(); 6    TreeNode node = root; 7    while (node != null || !stack.isEmpty()) { 8        while (node != null) { 9            stack.push(node);10            node = node.left;11        }12        if (!stack.isEmpty()) {13            node = stack.pop();14            //子节点交换15            TreeNode temp = node.left;16            node.left = node.right;17            node.right = temp;18            //注意这里以前是node.right,因为上面已经交换了19            //,所以这里要改为node.left20            node = node.left;21        }22    }23    return root;24}

递归方式解决

二叉树中序遍历的递归代码如下

1public void inOrderTraversal(TreeNode node) {2    if (node == null)3        return;4    inOrderTraversal(node.left);5    System.out.println(node.val);6    inOrderTraversal(node.right);7}

上面说了,只要能访问二叉树的每一个节点,然后交换左右子节点就行了,这里就以二叉树中序遍历递归的方式来看下

 1public TreeNode mirrorTree(TreeNode root) { 2    if (root == null) 3        return null; 4    mirrorTree(root.left); 5    //子节点交换 6    TreeNode temp = root.left; 7    root.left = root.right; 8    root.right = temp; 9    //上面交换过了,这里root.right要变成root.left10    mirrorTree(root.left);11    return root;12}

再来看一个后续遍历的

1public TreeNode mirrorTree(TreeNode root) {2    if (root == null)3        return null;4    TreeNode left = mirrorTree(root.left);5    TreeNode right = mirrorTree(root.right);6    root.left = right;7    root.right = left;8    return root;9}

总结

这题没什么难度,但解法比较多,主要是因为二叉树的遍历方式比较多,如果每一种方式递归和非递归都写的话就更多了。

●433,剑指 Offer-树的子结构

●414,剑指 Offer-重建二叉树

●403,验证二叉搜索树

●401,删除二叉搜索树中的节点

长按上图,识别图中二维码之后即可关注。

如果觉得有用就点个"赞"吧

本文分享自微信公众号 - 数据结构和算法(sjjghsf)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

评论

暂无评论