题解 | #输出二叉树的右视图#
输出二叉树的右视图
http://www.nowcoder.com/practice/c9480213597e45f4807880c763ddd5f0
主要知识点:根据前序+中序递归建树,层次遍历二叉树
import java.util.*;
public class Solution {
//根据前序+中序遍历重建二叉树
public TreeNode createByPreMid(int[] pre,int[] mid, int ipre,int imid,int n){
if(n==0)
return null;
TreeNode node = new TreeNode(0);
node.val = pre[ipre];
int i=0;
for(;i<n;++i){
if(pre[ipre]==mid[imid+i])
break;
}
node.left = createByPreMid(pre,mid,ipre+1,imid,i);
node.right = createByPreMid(pre,mid,ipre+i+1,imid+i+1,n-i-1);
return node;
}
//层次遍历
public ArrayList<Integer> levelOrder(TreeNode root){
ArrayList<Integer> arr = new ArrayList<>();
Deque<TreeNode> dq = new LinkedList<>();
dq.offer(root);
while(!dq.isEmpty()){
int curSize=dq.size();
while(curSize-->0){
TreeNode node = dq.poll();
if(curSize==0)
arr.add(node.val);
if(node.left!=null) dq.offer(node.left);
if(node.right!=null) dq.offer(node.right);
}
}
return arr;
}
public int[] solve (int[] xianxu, int[] zhongxu) {
// write code here
TreeNode root = createByPreMid(xianxu,zhongxu,0,0,xianxu.length);
ArrayList<Integer> arr = levelOrder(root);
int[] res = new int[arr.size()];
for(int i=0;i<arr.size();++i)
res[i] = arr.get(i);
return res;
}
}
阿勇算法解集 文章被收录于专栏
对一些基础的,经典的题目的算法题解,每道题的题解尽量做到一题多解,举一反三。其中每一个题解中,若是参考了其他牛人的想法,我会备注出来。