树-算法做题总结

白板写题和普通题的区别就是

1.需要自己自定义类和方法，基础结构一定不能写错，哪里是中括号，哪里是小括号

2.自定义Scanner输入，自己Sout输出打印结果

3.类名一般是Main，方法名一般自定义

算法：二叉树的遍历

题目要求：返回的是一个int数组，但是在树遍历中树的节点的数量是无法确定的，所以如果要返回int[]只能先用ArrayList存完再进行for转换。

一般来说可以这样写

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型一维数组
     */
    List<TreeNode> list = new ArrayList<>();
    public int[] postorderTraversal (TreeNode root) {
        // write code here
        if(root == null){
            return null;
        }
        postorderTraversal(root.left);
        postorderTraversal(root.right);
        list.add(root);
        int[] array = new int[list.size()];
        for(int i =0;i<list.size();i++){
            array[i] = list.get(i).val;
        }
        return array;
    }
}

但是我在写完之后发现对于传入的树为空时，返回的值是[]，但是方法里返回的是null，如果是面试手写要求可能没那么严格，但是写题时需要抽出来一个方法，来创建一个int[]，如果list为null，就返回一个空array，如果像上述的写法的话，如果传入的是空树，那么返回null，这个题的null是不能解析为[]的，必须返回的是一个空数组，所以需要腾出来一个方法。

算法：层序遍历和按之字形打印

前者采用的思路是队列（推荐）或者递归，不管是不是递归，时间和空间复杂度都是O(n)，注意之字形打印时还是借助队列，所以复杂度都还是O(n)

后者采用的思路是队列（推荐）或者是双栈（双栈本质上还是实现的队列），观察z字形的特征，可以发现可按照奇偶数的层序进行遍历，奇数正序偶数倒序

层序遍历如下

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     *
     * @param root TreeNode类
     * @return int整型ArrayList<ArrayList<>>
     */
    int count = 0;
    //Queue是Java中的队列接口，通常使用链表来实现这个接口，因为队列经常要插入删除，链表的插入删除时间复杂度比较小。
    //即将链表当作队列，FIFO
    Queue<TreeNode> queue = new LinkedList();
    ArrayList<ArrayList<Integer>> arrayList = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {

        //赋值运算符两端才会产生自动装箱拆箱
        queue.add(root);
        count ++;
        while(!queue.isEmpty()){
            //没遍历一层，就将list进行清空但是不能使用clear，所以每一次循环都new一个新的再添加，引用指向新的空ArrayList
            // （原本的对象不由list引用了，但是arrayList中有引用所以对象也不会被回收）
            ArrayList<Integer> list = new ArrayList<>();
//            queue.add(new Integer(root.val));
            while (count > 0){
                    TreeNode node = queue.element();
                    list.add(node.val);

                    if(node.left != null){
                        queue.add(node.left);
                    }
                    if(node.right != null){
                        queue.add(node.right);
                    }
                    queue.remove();
                    count --;
                }
            count = queue.size();
            arrayList.add(list);
            //用list.clear()方法清空list；用此方法，其它引用该list的值也会变成空,比如其他list中add了该list的元素即地址

            }


        return arrayList;
    }
}

Ps：单向队列方法是offer和poll，而双向deque的区别就是首位有对应的方法，即offerFirst和pollFirst

注意在创建变量时，下列语句

ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();

后面泛型可以简写为new ArrayList<>();但是不能写成new ArrayList>();

如果您喜欢此博客或发现它对您有用，则欢迎对此发表评论。也欢迎您共享此博客，以便更多人可以参与。如果博客中使用的图像侵犯了您的版权，请与作者联系以将其删除。谢谢！

算法：二叉树的遍历

算法：层序遍历和按之字形打印

层序遍历如下

注意在创建变量时，下列语句

特色标签

链友