leetcode算法题解(Java版)-1-二叉树遍历
又开始刷算法题了，正好在学Java，顺便也练练Java。 题目描述 Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between). For example:Given binary tree{3,9,20,#,#,15,7}, 3 / \ 9 20 / \ 15 7 return its zigzag level order traversal as: [ [3], [20,9], [15,7]] confused what"{1,#,2,3}"means? > read more on how binary tree is serialized on OJ. OJ's Binary Tree Serialization: The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below. Here's an example: 1 / \ 2 3 / 4 \ 5 The above binary tree is serialized as"{1,2,3,#,#,4,#,#,5}". 我的解答： /** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ import java.util.ArrayList; import java.util.LinkedList; import java.util.Collections; import java.util.Queue; public class Solution { public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) { ArrayList<ArrayList<Integer>> ans=new ArrayList<>(); if(root==null){ return ans; } ArrayList<Integer> tem=new ArrayList<>(); TreeNode lastNode=root; TreeNode levelNode=root; Queue<TreeNode> q=new LinkedList<>(); q.add(root); int cnt=0; while(q.size()!=0){ TreeNode poll=q.poll(); tem.add((Integer)poll.val); if(poll.left!=null){ q.offer(poll.left); lastNode=poll.left; } if(poll.right!=null){ q.offer(poll.right); lastNode=poll.right; } if(levelNode==poll){ if(cnt%2!=0){ Collections.reverse(tem); } levelNode=lastNode; ans.add(new ArrayList<>(tem)); tem.clear(); cnt++; } } return ans; } } 遇到的坑&&小结： 把Collections当成了Collection。实际上，Collections是一个包装类，可以当成专门为Collection中的类服务的工具类，不能被实例化；而Collection是根接口 Java引用变量有两个类型:一个是编译时的类型，一个是运行时的类型。编译时由声明该变量时使用的类型决定，运行时由实际赋值给它的对象的类型决定，当编译时的类型和运行时的类型不一样时，就产生了所谓的多态 在多态中，引用类型时接口或父类，而正真的实现类型是实现接口的类的对象或继承父类的子类对象。比如：Queue<TreeNode> q=new LinkedList<>();其中，引用类型是Queue这个接口，实现类型（也就是运行时的类型）是LinkedList这个实现了Queue接口的类 多态性是对象多种表现形式的体现 `ArrayList> res = new ArrayList>();一般都不这么写（我一开始不造），一般都写成ArrayList> res = new ArrayList<>();`因为不写默认跟前面的走，这是泛型规定的
