二叉樹的層次遍歷
題目：給定一個二叉樹，返回其按層次遍歷的節(jié)點值。 （即逐層地，從左到右訪問所有節(jié)點）。
例如:
給定二叉樹: [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
返回其層次遍歷結(jié)果：
[
[3],
[9,20],
[15,7]
]
思路：講真，這道題我好像也做過。記得是用了隊列輔助了。其實這個用list也是可以實現(xiàn)的，不過隊列本身先進先出，出去的時候直接彈出可以，而list就得順序讀取，讀取一個刪除一個。很麻煩。大概思路就是把每一層的樹存進去，然后遍歷，然后存值存list，本層全部取完存進結(jié)果集，同時每取一個元素要把下一層樹（先左后右）再存進去。。我去代碼實現(xiàn)了。
做完回來了，思路很清晰，我直接貼代碼：
/**
* 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;
}
}
然后我現(xiàn)在有點尷尬啊，，，性能只超過了百分之五，，，太打臉了，其實這個思路只要知道，還有很多數(shù)據(jù)結(jié)構(gòu)能做到的，比如我 之前說的list也可以，我不知道是不是我選擇的數(shù)據(jù)結(jié)構(gòu)有問題，，我先試試list實現(xiàn)，性能還不上來我就看別人的代碼了。
改成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，這個是鏈表結(jié)構(gòu)，所以獲取頭尾有現(xiàn)成的api：
然后這道題到這我就挺滿意了，這道題就到這里了，下一題。
二叉樹的矩形層次遍歷
題目：給定一個二叉樹，返回其節(jié)點值的鋸齒形層次遍歷。（即先從左往右，再從右往左進行下一層遍歷，以此類推，層與層之間交替進行）。
例如：
給定二叉樹 [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
返回鋸齒形層次遍歷如下：
[
[3],
[20,9],
[15,7]
]
思路：這道題其實就是上面那道題的演化版本，我感覺挺簡單的，在while循環(huán)中創(chuàng)建一個計數(shù)器，單數(shù)左往右，雙數(shù)右往左。閑話不說。我直接去實現(xiàn)了。
好了，實現(xiàn)完了，在做的時候有點小改動，比如計數(shù)器其實沒啥必要，我換成了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;
}
}
因為是在上題基礎(chǔ)上做的，所以很容易就實現(xiàn)啦，性能超過百分之九十八的人，所以也不復(fù)盤了，直接pass，下一題。
從前序與中序遍歷序列構(gòu)造二叉樹
題目：根據(jù)一棵樹的前序遍歷與中序遍歷構(gòu)造二叉樹。注意:你可以假設(shè)樹中沒有重復(fù)的元素。
例如，給出
前序遍歷 preorder = [3,9,20,15,7]
中序遍歷 inorder = [9,3,15,20,7]
返回如下的二叉樹：
3
/
9 20
/
15 7
思路：這道題有點意思，一點點理思路：首先前序排列，第一個數(shù)就是根節(jié)點，然后因為題目都說了每個元素沒有重復(fù)的，所以可以這么判斷樹結(jié)構(gòu)，中序的根節(jié)點左邊是左子樹的，右邊是右子樹的。然后下一層，在左子樹和右子樹范圍內(nèi)，前序遍歷中除了根節(jié)點應(yīng)該順序是左子樹-右子樹。上面的示例中左子樹直接葉子節(jié)點了，右子樹中20是第一個出現(xiàn)的（15,20,7中前序遍歷20第一個出現(xiàn)），所以20是右子樹的根節(jié)點，往下繼續(xù)這么判斷。其實就是個遞歸。我去嘗試寫一下代碼。
好了，做是做出來了，我自我感覺挺好的，雖然性能賊打臉，我先貼代碼：
/**
* 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;
//前序第一個元素是根節(jié)點
TreeNode res = new TreeNode(preorder[0]);
int idx = 0;
//找到根節(jié)點在中序遍歷中的下標
while(preorder[0]!=inorder[idx]) idx++;
//Arrays.copyOfRange(preorder,1,idx+1),因為前序第一個是根節(jié)點，所以從第二個也就是
//下標為1開始復(fù)制。因為含頭不含尾，所以最后到idx+1
//而中序則左右子樹在跟節(jié)點兩點，也就是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，只超過百分之四十。。其實我能想到的就是來回來去數(shù)組copy可能是性能不好的關(guān)鍵。我還是直接看看性能排行第一的代碼吧。
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){
//數(shù)組為空則返回null
if(pre==preorder.length){
return null;
}
//中序遍歷序列數(shù)組順序值等于終止值，則依次后移
//表示此節(jié)點為空
if(inorder[in]==stop){
in++;
return null;
}
//按照先序遍歷順序值新建節(jié)點
int val=preorder[pre++];
TreeNode root=new TreeNode(val);
//建立左節(jié)點，終止值為當前節(jié)點值
root.left=buildTree(preorder,inorder,val);
//建立右節(jié)點，終止值為上一節(jié)點值
root.right=buildTree(preorder,inorder,stop);
//返回當前節(jié)點
return root;
}
}
瞻仰瞻仰學習學習大神代碼吧。
然后今天的筆記就記到這里，如果稍微幫到你了記得點個喜歡點個關(guān)注，也祝大家工作順順利利！生活健健康康！
