Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
這題是求二叉樹的右視圖；我第一個想法就是用bfs呀初肉，跟binary tree level order traversal那題一樣的套路就行了坝辫，而bfs二叉樹我已經(jīng)爛熟于心了晌姚∥晃梗快速地寫了一下果然一次AC了棺棵。
public List<Integer> rightSideView(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) return res;
LinkedList<TreeNode> queue = new LinkedList<>();
queue.add(root);
int curNum = 1;
int nextNum = 0 ;
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
curNum -- ;
if (node.left!=null){
queue.offer(node.left);
nextNum ++ ;
}
if (node.right!=null){
queue.offer(node.right);
nextNum ++ ;
}
if (curNum==0){
res.add(node.val);
curNum = nextNum ;
nextNum = 0 ;
}
}
return res ;
}
晚上回來看看dfs之類的其他解法吧疮跑。上班去了以清。
下班回來了..
現(xiàn)在是晚上10:40分了，感覺也沒干什么突然間就這么晚了巫击。禀晓。六點半去健身，健身完了磨蹭了一下去吃了個飯九點才回家坝锰，回來做了一組腹肌訓練然后洗澡粹懒，就十點多了。顷级。有點煩啊凫乖。以后我決定中午去健身了，然后晚上早點回弓颈。
回到正題帽芽，剛才用dfs寫了一下，還是模仿的binary tree level order traversal的dfs寫法翔冀，dfs函數(shù)像這樣：
private void dfs(TreeNode root, int level, ArrayList<ArrayList<Integer>> list) {
if (root == null) return;
if (level >= list.size()) {
list.add(new ArrayList<Integer>());
}
list.get(level).add(root.val);
dfs(root.left, level + 1, list);
dfs(root.right, level + 1, list);
}
這么做需要O(n)的Space导街，因為需要把每一行的元素都存起來然后讀每個sublist的最后一個元素。
然后我去看了leetcode高票答案纤子，果然有奇淫巧技搬瑰。。如下：
public class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> result = new ArrayList<Integer>();
rightView(root, result, 0);
return result;
}
public void rightView(TreeNode curr, List<Integer> result, int currDepth){
if(curr == null){
return;
}
if(currDepth == result.size()){
result.add(curr.val);
}
rightView(curr.right, result, currDepth + 1);
rightView(curr.left, result, currDepth + 1);
}
}
乍一看有點難以理解控硼，跟dfs幾乎一樣泽论，但是不同的是它每次先遍歷右子樹，然后遍歷左子樹卡乾，然后把每層traverse到的第一個元素的val保存起來翼悴。空間復雜度O(logN)幔妨。
同理鹦赎，左視圖的話，就把這左右child 遞歸的順序換一下位置就好了误堡。
我就在想钙姊，既然如此是不是不需要遍歷左子樹了。埂伦。當然不行了煞额，因為遇到只有l(wèi)eft child的node的時候無法進入下一層呀。比如下面的case就不行。
Input:
[1,2]
Output:
[1]
Expected:
[1,2]
dfs（遞歸）跟tree結合真是非常完美膊毁，兩者都有層的概念胀莹。
那么，今天就到這里了婚温。晚安描焰。
