7月算法训练——第二十五天(树状数组)解题报告
题目类型:树状数组
题目难度:困难
第一题、327. 区间和的个数
- 题目链接:327. 区间和的个数
- 思路分析:
树状数组这题有点看不懂,先占个位
剑指offer
题目类型:广度优先算法
第二题、剑指 Offer 32 – I. 从上到下打印二叉树
- 题目链接:剑指 Offer 32 – I. 从上到下打印二叉树
- 思路分析:
定义一个队列,当遍历完一个节点时,就将该节点的左右节点加入队列,当将每一个节点的值加入ArrayList数组中,再将ArrayList转化为int数组返回。这里根据队列的先进先出的特性,结果的顺序和二叉树的层序遍历结果是一样的。 - 代码:
class Solution {
public int[] levelOrder(TreeNode root) {
if(root == null){return new int[0];}
ArrayList<Integer> list = new ArrayList();
Queue<TreeNode> que = new LinkedList(){{add(root);}};
while(!que.isEmpty()){
TreeNode node = que.poll();
list.add(node.val);
if(node.left != null){que.add(node.left);}
if(node.right != null){que.add(node.right);}
}
int[] a = new int[list.size()];
for(int i = 0; i < list.size(); i++){
a[i] = list.get(i);
}
return a;
}
}
第三题、剑指 Offer 32 – II. 从上到下打印二叉树 II
- 题目链接:剑指 Offer 32 – II. 从上到下打印二叉树 II
- 思路分析:
这一题和上一题差不多,比上一题稍微多一点,就是在遍历完二叉树的一层是,要将这个list集合加入到结果中,所以要有一个for循环来让当前层中所有的节点的值都加入到ArrayList中,当这一层循环完,再将这个list集合加入到结果中。 - 代码:
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ll = new ArrayList();
if(root == null){return ll;}
Queue<TreeNode> que = new LinkedList();
que.offer(root);
while(!que.isEmpty()){
// TreeNode node = que.poll();
List<Integer> list = new ArrayList();
int size = que.size();
for(int i = 1; i <= size; i++){
TreeNode node = que.poll();
list.add(node.val);
if(node.left != null){
que.offer(node.left);
}
if(node.right != null){
que.offer(node.right);
}
}
ll.add(list);
}
return ll;
}
}
第四题、剑指 Offer 32 – III. 从上到下打印二叉树 III
- 题目链接:剑指 Offer 32 – III. 从上到下打印二叉树 III
- 思路分析:
这一题又在上一题的基础上多加了这一层要逆序输出,本来我想要将上一题中的队列换成栈,但突然发现一个问题就是,栈的进出都是从栈顶一侧操作的,等于说栈底这一侧是无法操作的,所以这种方法不可行。还是要用队列,因为队列中队头和队尾都可以操作,两端都可以操作使队列还是十分适合本题。具体方法是要判断当前层是奇数层还是偶数层,奇数层(层数从0开始)要从后往前遍历,偶数层从前往后遍历,遍历完一层要将结果加入到结果中。 - 代码:
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ll = new ArrayList();
if(root == null){return ll;}
Queue<TreeNode> que = new LinkedList();
que.offer(root);
while(!que.isEmpty()){
// TreeNode node = que.poll();
LinkedList<Integer> list = new LinkedList();
int size = que.size();
for(int i = 1; i <= size; i++){
TreeNode node = que.poll();
// list.add(node.val);
if(ll.size() % 2 != 0){
list.addFirst(node.val);
}else{
list.addLast(node.val);
}
if(node.left != null){
que.offer(node.left);
}
if(node.right != null){
que.offer(node.right);
}
}
ll.add(list);
}
return ll;
}
}
文章出处登录后可见!
已经登录?立即刷新