二叉樹的層次遍歷
題目：給定一個二叉樹圆存，返回其按層次遍歷的節(jié)點值。 （即逐層地指郁，從左到右訪問所有節(jié)點）踊餐。
例如:
給定二叉樹: [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
返回其層次遍歷結果：
[
[3],
[9,20],
[15,7]
]
思路：講真，這道題我好像也做過欲侮。記得是用了隊列輔助了崭闲。其實這個用list也是可以實現(xiàn)的，不過隊列本身先進先出威蕉，出去的時候直接彈出可以镀脂，而list就得順序讀取，讀取一個刪除一個忘伞。很麻煩。大概思路就是把每一層的樹存進去沙兰，然后遍歷氓奈，然后存值存list，本層全部取完存進結果集鼎天，同時每取一個元素要把下一層樹（先左后右）再存進去舀奶。。我去代碼實現(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ù)結構能做到的，比如我 之前說的list也可以弱左，我不知道是不是我選擇的數(shù)據(jù)結構有問題窄陡，，我先試試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，這個是鏈表結構邪意，所以獲取頭尾有現(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;
}
}
因為是在上題基礎上做的河劝，所以很容易就實現(xiàn)啦，性能超過百分之九十八的人矛紫，所以也不復盤了赎瞎，直接pass，下一題颊咬。
從前序與中序遍歷序列構造二叉樹
題目：根據(jù)一棵樹的前序遍歷與中序遍歷構造二叉樹务甥。注意:你可以假設樹中沒有重復的元素牡辽。
例如，給出
前序遍歷 preorder = [3,9,20,15,7]
中序遍歷 inorder = [9,3,15,20,7]
返回如下的二叉樹：
3
/
9 20
/
15 7
思路：這道題有點意思敞临，一點點理思路：首先前序排列态辛，第一個數(shù)就是根節(jié)點，然后因為題目都說了每個元素沒有重復的挺尿，所以可以這么判斷樹結構奏黑，中序的根節(jié)點左邊是左子樹的，右邊是右子樹的编矾。然后下一層熟史，在左子樹和右子樹范圍內(nèi)，前序遍歷中除了根節(jié)點應該順序是左子樹-右子樹窄俏。上面的示例中左子樹直接葉子節(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開始復制传泊。因為含頭不含尾，所以最后到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可能是性能不好的關鍵祖能。我還是直接看看性能排行第一的代碼吧歉秫。
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;
}
}
瞻仰瞻仰學習學習大神代碼吧轧膘。
然后今天的筆記就記到這里，如果稍微幫到你了記得點個喜歡點個關注兔甘，也祝大家工作順順利利谎碍！生活健健康康！
