199.二叉树的右视图
给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:
1 <---
/
2 3 <---
5 4 <---
利用层次遍历寻找二叉树中的右视图（层次遍历，一次外循环遍历一层的节点，每层中最后一个访问的节点就是右视图的节点）
public List<Integer> rightSideView(TreeNode root) {
if(root == null){
return new ArrayList<Integer>();
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
ArrayList<Integer> resList = new ArrayList<>();
while (!queue.isEmpty()){
int size = queue.size();
while (size > 0){
TreeNode node = queue.poll();
if (size == 1){
resList.add(node.val);
}
if (node.left != null){
queue.offer(node.left);
}
if (node.right != null){
queue.offer(node.right);
}
size--;
}
}
return resList;
}
NC.136
请根据二叉树的前序遍历，中序遍历恢复二叉树，并打印出二叉树的右视图
右视图：给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:
1 <---
/
2 3 <---
5 4 <---
思路：
1、依据先序遍历和中序遍历的结果重建二叉树；
2、利用层次遍历寻找二叉树中的右视图（层次遍历，一次外循环遍历一层的节点，每层中最后一个访问的节点就是右视图的节点）
public int[] solve (int[] xianxu, int[] zhongxu) {
// write code here
TreeNode root = rebuildTree(xianxu,zhongxu,0,xianxu.length-1,0,zhongxu.length-1);
return levelTrace(root);
}
private TreeNode rebuildTree(int[] xianxu, int[] zhongxu,int l1,int r1,int l2,int r2){
if (l1 > r1 || l2 > r2){
return null;
}
int rootValue = xianxu[l1];
int rootInOrderIndex = -1;
TreeNode root = new TreeNode(rootValue);
for (int i = l2; i <= r2; i++) {
if (rootValue == zhongxu[i]){
rootInOrderIndex = i;
break;
}
}
int leftLength = rootInOrderIndex - l2;
root.left = rebuildTree(xianxu,zhongxu,l1+1,l1+leftLength,l2,rootInOrderIndex-1);
root.right = rebuildTree(xianxu,zhongxu,l1+leftLength+1,r1,rootInOrderIndex+1,r2);
return root;
}
private int[] levelTrace(TreeNode root){
if (root == null){
return new int[]{};
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
ArrayList<Integer> resList = new ArrayList<>();
while (!queue.isEmpty()){
int size = queue.size();
while (size > 0){
TreeNode node = queue.poll();
if (size == 1){
resList.add(node.val);
}
if (node.left != null){
queue.offer(node.left);
}
if (node.right != null){
queue.offer(node.right);
}
size--;
}
}
int[] res = new int[resList.size()];
for (int i = 0; i < resList.size(); i++) {
res[i] = resList.get(i);
}
return res;
}