二叉树的层次遍历
题目：给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
返回其层次遍历结果：
[
[3],
[9,20],
[15,7]
]
思路：讲真，这道题我好像也做过。记得是用了队列辅助了。其实这个用list也是可以实现的，不过队列本身先进先出，出去的时候直接弹出可以，而list就得顺序读取，读取一个删除一个。很麻烦。大概思路就是把每一层的树存进去，然后遍历，然后存值存list，本层全部取完存进结果集，同时每取一个元素要把下一层树（先左后右）再存进去。。我去代码实现了。
做完回来了，思路很清晰，我直接贴代码：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
Queue<TreeNode> queue = new LinkedBlockingQueue<TreeNode>();
List<List<Integer>> res = new ArrayList<List<Integer>>();
if(root==null) return res;
queue.add(root);
while(!queue.isEmpty()){
int size = queue.size();
List<Integer> list = new ArrayList<Integer>();
for(int i = 0;i<size;i++){
TreeNode n = queue.poll();
list.add(n.val);
if(n.left!=null) queue.add(n.left);
if(n.right!=null) queue.add(n.right);
}
res.add(list);
}
return res;
}
}
然后我现在有点尴尬啊，，，性能只超过了百分之五，，，太打脸了，其实这个思路只要知道，还有很多数据结构能做到的，比如我 之前说的list也可以，我不知道是不是我选择的数据结构有问题，，我先试试list实现，性能还不上来我就看别人的代码了。
改成LinkedList（这个list自带removeFirst方法）性能大大的提升了，从7,8ms变成了1ms。。超过了百分之九十七的人了，我先把代码贴出来：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
LinkedList<TreeNode> d = new LinkedList<TreeNode>();
List<List<Integer>> res = new ArrayList<List<Integer>>();
if(root==null) return res;
d.add(root);
while(d.size()!=0){
int size = d.size();
List<Integer> list = new ArrayList<Integer>();
for(int i = 0;i<size;i++){
TreeNode n = d.removeFirst();
list.add(n.val);
if(n.left!=null) d.add(n.left);
if(n.right!=null) d.add(n.right);
}
res.add(list);
}
return res;
}
}
顺便说一下这个LinkedList的源码，有获取第一个获取最后一个之类的，是个很方便的类，不同于ArrayList，这个是链表结构，所以获取头尾有现成的api：
然后这道题到这我就挺满意了，这道题就到这里了，下一题。
二叉树的矩形层次遍历
题目：给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
例如：
给定二叉树 [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
返回锯齿形层次遍历如下：
[
[3],
[20,9],
[15,7]
]
思路：这道题其实就是上面那道题的演化版本，我感觉挺简单的，在while循环中创建一个计数器，单数左往右，双数右往左。闲话不说。我直接去实现了。
好了，实现完了，在做的时候有点小改动，比如计数器其实没啥必要，我换成了flag 布尔值来判断，更方便，然后true是正着添加，false是addFist也就是反着添加，我直接贴代码：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res =new ArrayList<List<Integer>>();
if(root==null) return res;
LinkedList<TreeNode> d = new LinkedList<TreeNode>();
d.add(root);
boolean flag = true;
while(d.size()!=0){
int size = d.size();
LinkedList<Integer> list = new LinkedList<Integer>();
for(int i = 0;i<size;i++){
TreeNode n = d.removeFirst();
if(flag){
list.add(n.val);
}else{
list.addFirst(n.val);
}
if(n.left!=null) d.add(n.left);
if(n.right!=null) d.add(n.right);
}
flag = !flag;
res.add(list);
}
return res;
}
}
因为是在上题基础上做的，所以很容易就实现啦，性能超过百分之九十八的人，所以也不复盘了，直接pass，下一题。
从前序与中序遍历序列构造二叉树
题目：根据一棵树的前序遍历与中序遍历构造二叉树。注意:你可以假设树中没有重复的元素。
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
3
/
9 20
/
15 7
思路：这道题有点意思，一点点理思路：首先前序排列，第一个数就是根节点，然后因为题目都说了每个元素没有重复的，所以可以这么判断树结构，中序的根节点左边是左子树的，右边是右子树的。然后下一层，在左子树和右子树范围内，前序遍历中除了根节点应该顺序是左子树-右子树。上面的示例中左子树直接叶子节点了，右子树中20是第一个出现的（15,20,7中前序遍历20第一个出现），所以20是右子树的根节点，往下继续这么判断。其实就是个递归。我去尝试写一下代码。
好了，做是做出来了，我自我感觉挺好的，虽然性能贼打脸，我先贴代码：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if(preorder.length==0) return null;
//前序第一个元素是根节点
TreeNode res = new TreeNode(preorder[0]);
int idx = 0;
//找到根节点在中序遍历中的下标
while(preorder[0]!=inorder[idx]) idx++;
//Arrays.copyOfRange(preorder,1,idx+1),因为前序第一个是根节点，所以从第二个也就是
//下标为1开始复制。因为含头不含尾，所以最后到idx+1
//而中序则左右子树在跟节点两点，也就是0-idx-1个都是左子树的，所以这里直接0-idx
res.left = buildTree(Arrays.copyOfRange(preorder,1,idx+1),Arrays.copyOfRange(inorder,0,idx));
res.right = buildTree(Arrays.copyOfRange(preorder,idx+1,preorder.length),Arrays.copyOfRange(inorder,idx+1,inorder.length));
return res;
}
}
因为这个我思路也不是很顺，一直改，所以我注释写的比较清楚，就不多解释什么了。性能12ms，只超过百分之四十。。其实我能想到的就是来回来去数组copy可能是性能不好的关键。我还是直接看看性能排行第一的代码吧。
class Solution {
private int pre=0;
private int in=0;
public TreeNode buildTree(int [] preorder, int [] inorder) {
return buildTree(preorder,inorder,Integer.MAX_VALUE+1);
}
public TreeNode buildTree(int [] preorder,int [] inorder,long stop){
//数组为空则返回null
if(pre==preorder.length){
return null;
}
//中序遍历序列数组顺序值等于终止值，则依次后移
//表示此节点为空
if(inorder[in]==stop){
in++;
return null;
}
//按照先序遍历顺序值新建节点
int val=preorder[pre++];
TreeNode root=new TreeNode(val);
//建立左节点，终止值为当前节点值
root.left=buildTree(preorder,inorder,val);
//建立右节点，终止值为上一节点值
root.right=buildTree(preorder,inorder,stop);
//返回当前节点
return root;
}
}
瞻仰瞻仰学习学习大神代码吧。
然后今天的笔记就记到这里，如果稍微帮到你了记得点个喜欢点个关注，也祝大家工作顺顺利利！生活健健康康！
