共计 5590 个字符,预计需要花费 14 分钟才能阅读完成。
前言阐明
算法学习,日常刷题记录。
题目连贯
翻转二叉树
题目内容
翻转一棵二叉树。
示例:
输出:
输入:
备注:
这个问题是受到 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 后盾曾经帮你做了转换,然而如果咱们要本人写出残缺代码,须要本人做转换。
这里只给出一个数组就确定了二叉树,证实是层序遍历,因为前序遍历、中序遍历、后序遍历都无奈独自一个数组就推导出二叉树,层序遍历能力独自一个数组推导出二叉树。
层序遍历:逐层从上到下,每层从左到右拜访所有节点。
为不便了解,上面举例几个:
输出数组 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<TreeNode> queue = new LinkedList<>();
// 先把二叉树根节点放进队列最初
queue.add(root);
// 遍历数组,结构二叉树
while (i < nums.length) {
// 队列出列第一个元素,获取以后二叉树节点
current = queue.poll();
// 获取数组的值,数组下标加 1
value = 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<Integer>> list = new ArrayList<>();
if (root == null) {
// 若二叉树节点为空,间接返回空数组
return new Integer[0];
}
// 通过队列辅助,从上到下实现每层的遍历,在每层遍历时,每遍历完一个节点,就确定这个节点的两个子节点,如果不为空,把子节点放进队列前面,队列保障了树依照档次从上到下遍历,每层从左到右遍历
// 定义队列
Queue<TreeNode> queue = new LinkedList<>();
// 先把二叉树的根节点放进队列最初
queue.add(root);
// 循环,直到队列的长度为零,完结循环
while (queue.size() > 0) {
// 定义内层列表,保留内层后果
List<Integer> 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<Integer> row : list) {
// 每行列表的长度累加
count += row.size();}
// 定义数组
Integer[] nums = new Integer[count];
// 定义数组的下标
int n = 0;
// 遍历两层列表,把两层列表转为数组
for (List<Integer> 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…
原文链接
原文链接:翻转二叉树