LeetCode刷题-我会翻转二叉树，谷歌还要我吗（）算法javaleetcode

前言说明
算法学习，日常刷题记录。
题目连接
翻转二叉树
题目内容
翻转一棵二叉树。

示例:
输入：

文章图片

输出：

文章图片

备注:
这个问题是受到Max Howell的原问题启发的：
谷歌：我们90％的工程师使用您编写的软件(Homebrew)，但是您却无法在面试时在白板上写出翻转二叉树这道题，这太糟糕了。

分析过程
翻转二叉树很简单，可以使用递归法。
把二叉树看成是根节点、左孩子、右孩子的整体，整体翻转根节点的左孩子和右孩子。
如果左孩子和右孩子也是树，那么递归下去同样执行相同的方法，直到左孩子和右孩子为空时，递归开始回溯。
最后返回二叉树的根节点，就是翻转后的二叉树。
解答代码

/** * Definition for a binary tree node. * public class TreeNode { *int val; *TreeNode left; *TreeNode right; *TreeNode() {} *TreeNode(int val) { this.val = val; } *TreeNode(int val, TreeNode left, TreeNode right) { *this.val = val; *this.left = left; *this.right = right; *} * } */ class Solution { public TreeNode invertTree(TreeNode root) { if (root == null) { // 若树节点是空，直接返回空 return null; }// 利用递归法，把树看成是根节点、左孩子、右孩子的整体，整体翻转根节点的左孩子和右孩子，如果左孩子和右孩子也是树，那么递归下去同样执行相同的方法，直到左孩子和右孩子为空时，递归开始回溯// 获取根节点的左孩子 TreeNode left = invertTree(root.left); // 根节点的左孩子等于右孩子，右孩子等于左孩子，实现翻转 root.left = invertTree(root.right); root.right = left; // 返回翻转后的根节点 return root; } }

提交结果
执行用时0ms，时间击败100.00%的用户，内存消耗35.9MB，空间击败37.33%的用户。

文章图片

原来翻转二叉树这么简单，我会翻转二叉树，谷歌还要我吗？

延伸分析
但是，我这个人刷题都会把完整的代码写出来，上面的明显不是完整代码，我们在执行运行时，输入的是一个数组，输出的也是一个数组，如图：

文章图片

而invertTree方法实质输入的是一个二叉树TreeNode对象，所以这里其实存在一个数组转换为二叉树的输入过程，还有一个二叉树转换回数组的输出过程，在LeetCode上刷题时LeetCode后台已经帮你做了转换，但是如果我们要自己写出完整代码，需要自己做转换。
【LeetCode刷题-我会翻转二叉树，谷歌还要我吗（）】这里只给出一个数组就确定了二叉树，证明是层序遍历，因为前序遍历、中序遍历、后序遍历都无法单独一个数组就推导出二叉树，层序遍历才能单独一个数组推导出二叉树。
层序遍历：逐层从上到下，每层从左到右访问所有节点。
为方便理解，下面举例几个：
输入数组1：[0,null,2,null,4,null,6]
输出二叉树1：

文章图片

输入数组2：[1,null,2,3]
输出二叉树2：

文章图片

输入数组3：[0,1,null,null,4]
输出二叉树3：

文章图片

输入数组4：[4,2,7,1,3,6,9]
输出二叉树4：

文章图片

数组转为二叉树：有点奇怪的是，我翻了很多算法书本，查阅了很多网上资料，很少看到有提及如何把层序遍历的数组转为二叉树的，下面我整理出了一个转换的方法，请看后面的完整代码arrayToTreeNode方法，通过队列辅助来实现广度优先搜索，即模拟层序遍历时从上到下从左到右的过程，把数组转换为二叉树，要注意考虑数组元素为null的情况，当数组元素为null时，该节点没有孩子，但是自身会占用一个数组元素。
二叉树转为数组：请看后面的完整代码treeNodeToArray方法，也是通过队列辅助来实现广度优先搜索，即模拟层序遍历时从上到下从左到右的过程，先把二叉树转换为两层列表List，两层列表的每一层保存一层树的从左到右的节点值，最后再把两层列表List转换为数组，这里也要注意数组元素为null的情况，若一行元素都为null，那么这一行不要；若一行元素最后一个为null，要去掉最后一个元素。
完整代码如下：

import java.util.*; public class Main {public static void main(String[] args) { // 获取输入结果 Scanner scanner = new Scanner(System.in); String str = scanner.next(); scanner.close(); // 处理输入结果 Integer[] nums; if ("[]".equals(str)) { // 当数组为空 nums = null; } else { // 当数组不为空 String[] strs = str.split("\\[")[1].split("]")[0].split(","); int size = strs.length; nums = new Integer[size]; for (int i = 0; i < size; ++i) { if ("null".equals(strs[i])) { nums[i] = null; } else { nums[i] = Integer.parseInt(strs[i]); } } }// 数组转为二叉树 TreeNode root = arrayToTreeNode(nums); // 获取输出结果 TreeNode result = invertTree(root); System.out.println(Arrays.toString(treeNodeToArray(result))); }// 数组转为二叉树，层序遍历，分层按照从上到下，从左到右的顺序 private static TreeNode arrayToTreeNode(Integer[] nums) { // 利用队列辅助，特别需要注意支持数组元素为null，当数组元素为null时，该节点没有孩子，但是自身会占用一个数组元素 // 如果该节点的左孩子为null，右孩子不为null，那么数组的下一个元素会从右孩子的子节点开始，因为左孩子为null，没有子节点 // 例子：[0,null,2,null,4,null,6]，[1,null,2,3]，[0,1,null,null,4]，[4,2,7,1,3,6,9]if (nums == null || nums.length == 0) { // 若二叉树节点为空，直接返回空 return null; }// 数组的开始下标 int i = 1; // 先构造二叉树根节点 TreeNode root = new TreeNode(nums[0]); // 定义当前的二叉树节点，保存临时值 TreeNode current; // 定义当前数组的值 Integer value; // 定义队列，层序遍历创建二叉树 Queue queue = new LinkedList<>(); // 先把二叉树根节点放进队列最后 queue.add(root); // 遍历数组，构造二叉树 while (i < nums.length) { // 队列出列第一个元素，获取当前二叉树节点 current = queue.poll(); // 获取数组的值，数组下标加1 value = https://www.it610.com/article/nums[i++]; if (value != null) { // 创建当前二叉树节点的左孩子 TreeNode left = new TreeNode(value); if (current != null) { // 构造当前二叉树节点的左孩子 current.left = left; }// 把当前二叉树节点的左孩子放进队列最后 queue.add(left); }if (i < nums.length) { // 获取数组的值，数组下标加1 value = nums[i++]; if (value != null) { // 创建当前二叉树节点的右孩子 TreeNode right = new TreeNode(value); if (current != null) { // 构造当前二叉树节点的右孩子 current.right = right; }// 把当前二叉树节点的右孩子放进队列最后 queue.add(right); } } }// 返回二叉树的根节点 return root; }// 二叉树转为数组，层序遍历，分层按照从上到下，从左到右的顺序，这里因为是翻转二叉树，需要特殊处理，最后一层空的节点也要显示出来，显示为null，这样才能看出翻转后的二叉树的效果 private static Integer[] treeNodeToArray(TreeNode root) { // 定义两层列表，保存整体结果 List> list = new ArrayList<>(); if (root == null) { // 若二叉树节点为空，直接返回空数组 return new Integer[0]; }// 通过队列辅助，从上到下完成每层的遍历，在每层遍历时，每遍历完一个节点，就确定这个节点的两个子节点，如果不为空，把子节点放进队列后面，队列保证了树按照层次从上到下遍历，每层从左到右遍历// 定义队列 Queue queue = new LinkedList<>(); // 先把二叉树的根节点放进队列最后 queue.add(root); // 循环，直到队列的长度为零，结束循环 while (queue.size() > 0) { // 定义内层列表，保存内层结果 List temp = new ArrayList<>(); // 获取队列的长度 int size = queue.size(); // 遍历队列，每次遍历完成一层树节点的遍历 for (int i = 0; i < size; ++i) { // 队列出列第一个元素 TreeNode node = queue.poll(); if (node != null) { // 把出列的元素的值添加到内层列表 temp.add(node.val); if (node.left != null) { // 把当前二叉树节点的左孩子放进队列最后 queue.add(node.left); } else { // 子节点为空也要放进队列最后，为了适应看出翻转二叉树后的效果 queue.add(null); }if (node.right != null) { // 把当前二叉树节点的右孩子放进队列最后 queue.add(node.right); } else { // 子节点为空也要放进队列最后，为了适应看出翻转二叉树后的效果 queue.add(null); } } else { // 把空值添添加到内层列表，为了适应看出翻转二叉树后的效果 temp.add(null); } }// 内层列表是否全部元素都是空 boolean isAllNull = true; // 判断内层列表是否全部元素都是空，如果全部元素都是空，那么这一行的内层列表数据是多出的 for (Integer col : temp) { if (col != null) { // 只要有一个元素不是空，那么就不是全部元素都是空 isAllNull = false; break; } }if (!isAllNull) { // 不是全部元素都是空的内层列表，才添加进两层列表 list.add(temp); } }// 打印两层列表形式的层序遍历结果 System.out.println("treeNodeToArray list:" + list); // 定义数组的长度 int count = 0; // 遍历两层列表，计算出数组的长度 for (List row : list) { // 每行列表的长度累加 count += row.size(); }// 定义数组 Integer[] nums = new Integer[count]; // 定义数组的下标 int n = 0; // 遍历两层列表，把两层列表转为数组 for (List row : list) { for (Integer col : row) { nums[n++] = col; } }if (nums[nums.length - 1] == null) { // 若最后一个元素是null，删除最后一个元素，这种情况肯定是null落在右节点上，而且最后的位置，最后一个元素是null不要保留，如果null在左边才是要保留的 return Arrays.copyOf(nums, nums.length - 1); }// 返回数组 return nums; }// 翻转二叉树 private static TreeNode invertTree(TreeNode root) { if (root == null) { // 若树节点是空，直接返回空 return null; }// 利用递归法，把树看成是根节点、左孩子、右孩子的整体，整体翻转根节点的左孩子和右孩子，如果左孩子和右孩子也是树，那么递归下去同样执行相同的方法，直到左孩子和右孩子为空时，递归开始回溯// 获取根节点的左孩子 TreeNode left = invertTree(root.left); // 根节点的左孩子等于右孩子，右孩子等于左孩子，实现翻转 root.left = invertTree(root.right); root.right = left; // 返回翻转后的根节点 return root; }}// 定义二叉树 class TreeNode {int val; TreeNode left; TreeNode right; TreeNode() { }TreeNode(int val) { this.val = val; }TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; }}

完整代码获取：https://github.com/zjhpure/al...
原文链接
原文链接：翻转二叉树