7月算法训练——第二十五天（树状数组）解题报告

7月算法训练——第二十五天（树状数组）解题报告

题目类型：树状数组
题目难度：困难

第一题、327. 区间和的个数

1. 题目链接：327. 区间和的个数
   
2. 思路分析：
   树状数组这题有点看不懂，先占个位
   剑指offer
   题目类型：广度优先算法

第二题、剑指 Offer 32 – I. 从上到下打印二叉树

1. 题目链接：剑指 Offer 32 – I. 从上到下打印二叉树
2. 思路分析：
   定义一个队列，当遍历完一个节点时，就将该节点的左右节点加入队列，当将每一个节点的值加入ArrayList数组中，再将ArrayList转化为int数组返回。这里根据队列的先进先出的特性，结果的顺序和二叉树的层序遍历结果是一样的。
3. 代码：

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

1. 题目链接：剑指 Offer 32 – II. 从上到下打印二叉树 II
2. 思路分析：
   这一题和上一题差不多，比上一题稍微多一点，就是在遍历完二叉树的一层是，要将这个list集合加入到结果中，所以要有一个for循环来让当前层中所有的节点的值都加入到ArrayList中，当这一层循环完，再将这个list集合加入到结果中。
3. 代码：

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

1. 题目链接：剑指 Offer 32 – III. 从上到下打印二叉树 III
2. 思路分析：
   这一题又在上一题的基础上多加了这一层要逆序输出，本来我想要将上一题中的队列换成栈，但突然发现一个问题就是，栈的进出都是从栈顶一侧操作的，等于说栈底这一侧是无法操作的，所以这种方法不可行。还是要用队列，因为队列中队头和队尾都可以操作，两端都可以操作使队列还是十分适合本题。具体方法是要判断当前层是奇数层还是偶数层，奇数层（层数从0开始）要从后往前遍历，偶数层从前往后遍历，遍历完一层要将结果加入到结果中。
3. 代码：

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;
    }
}