脚本宝典收集整理的这篇文章主要介绍了算法刷题打卡(十四),脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
102. 二叉树的层序遍历 - 力扣(LeetCode) (leetcode-cn.COM)
给你一个二叉树,请你返回其按 层序遍历 得到的节点值。 (即逐层地,从左到右访问所有节点)。
示例F1a; 二叉树:[3,9,20,null,null,15,7],
3
/
9 20
/
15 7
返回其层序遍历结果:
[
[3],
[9,20],
[15,7]
]
//宽度优先 按层遍历
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ans = new ArrayList<>();
if (root == null) {
return ans;
}
LinkedList<TreeNode> queue = new LinkedList<>();
queue.add(root);
int size = 0;
while (!queue.iSEMpty()) {//不为空
List<Integer> level = new ArrayList<>();
size = queue.size();
for (int i = 0; i < size; i++) {//此层答案
TreeNode cur = queue.pollLast();
level.add(cur.val);
if (cur.left != null) {//添加左
queue.addFirst(cur.left);
}
if (cur.right != null) {//右
queue.adDFirst(cur.right);
}
}
ans.add(level);
}
return ans;
}
103. 二叉树的锯齿形层序遍历 - 力扣(LeetCode) (leetcode-cn.com)
给定一个二叉树,返回其节点值的锯齿形层序遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。
例如: 给定二叉树 [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
返回锯齿形层序遍历如下:
[
[3],
[20,9],
[15,7]
]
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> ans = new ArrayList<>();
if (root == null) {
return ans;
}
LinkedList<TreeNode> queue = new LinkedList<>();
queue.add(root);
boolean isFlag = true;//判断头尾的过程
int size = 0;
while (!queue.isEmpty()) {
List<Integer> level = new ArrayList<>();
size = queue.size();
for (int i = 0; i < size; i++) {
//头过程 头出尾进 尾 : 尾出头进
TreeNode cur = isFlag ? queue.pollFirst() : queue.pollLast();
level.add(cur.val);
if (isFlag) {
if (cur.left != null) {
queue.addLast(cur.left);
}
if (cur.right != null) {
queue.addLast(cur.right);
}
} else {
if (cur.right != null) {
queue.addFirst(cur.right);
}
if (cur.left != null) {
queue.addFirst(cur.left);
}
}
}
ans.add(level);
isFlag = !isFlag;
}
return ans;
}
104. 二叉树的最大深度 - 力扣(LeetCode) (leetcode-cn.com)
给定一个二叉树,找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例: 给定二叉树 [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
返回它的最大深度 3 。
public int maxDepth(TreeNode root) {
if(root == null){
return 0;
}
int left = maxDepth(root.left);
int right = maxDepth(root.right);
return Math.max(left,right) + 1;
}
105. 从前序与中序遍历序列构造二叉树 - 力扣(LeetCode) (leetcode-cn.com)
给定一棵树的前序遍历 PReorder 与中序遍历 inorder。请构造二叉树并返回其根节点。
示例 1:
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] Output: [3,9,20,null,null,15,7] 示例 2:
Input: preorder = [-1], inorder = [-1] Output: [-1]
//递归
public TreeNode buildTree(int[] preorder, int[] inorder) {
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < inorder.length; i++) {
map.put(inorder[i], i);
}
return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, map);
}
//先序 [头[左树][右树]] 中序[[左树]头[右树]] map 值在那个位置
public static TreeNode build(int[] preorder, int pl, int pr, int[] inorder, int il, int ir, HashMap<Integer, Integer> map) {
if (pl > pr) {
return null;
}
TreeNode head = new TreeNode(preorder[pl]);
if (pl == pr) {
return head;
}
int headIndex = map.get(preorder[pl]);//头节点下标
// 划分 左右子树的区间
head.left = build(preorder, pl + 1, pl + headIndex - il, inorder, il, headIndex - 1, map);
head.right = build(preorder, pl + headIndex - il + 1, pr, inorder, headIndex + 1, ir, map);
return head;
}
以上是脚本宝典为你收集整理的算法刷题打卡(十四)全部内容,希望文章能够帮你解决算法刷题打卡(十四)所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。