力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
请根据二叉树的前序遍历，中序遍历恢复二叉树，并打印出二叉树的右视图
示例 1:
输入: [1,2,3,null,5,null,4] 输出: [1,3,4]
- 想一想，从右往左看，看到的节点都有哪些特点呢？每一层都能且只能看到一个节点，且这个节点是每一层的最后一个节点。
- 根据上面的分析，很显然用二叉树的层序遍历就行了当遇到每一层的最后一个节点时，就把该节点添加到结果数组即可。
这个添加时机是在中序位置还是后序？Q 前序？
左右中，在后续位置
public int[] solve (int[] preOrder, int[] inOrder) {
// write code here
ArrayList<Integer> res = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
TreeNode root = reConstructBinaryTree(preOrder, inOrder);
queue.add(root);
if (preOrder.length == 0 || inOrder.length == 0) return new int[0];
while (!queue.isEmpty()) {
int n = queue.size();
while (n-- > 0) {
TreeNode temp = queue.poll();
//最右元素
if (n == 0)
res.add(temp.val);
if (temp.left != null)
queue.offer(temp.left);
if (temp.right != null)
queue.offer(temp.right);
}
}
int n = res.size();
int[] array = new int[n];
for (int i = 0; i < n; ++i) {
array[i] = res.get(i);
}
return array;
}
public TreeNode reConstructBinaryTree (int[] preOrder, int[] inOrder) {
// write code here
int n = preOrder.length;
int m = inOrder.length;
if (n == 0 || m == 0) return null;
TreeNode root = new TreeNode(preOrder[0]);
for (int i = 0; i < inOrder.length; i++) {
if (preOrder[0] == inOrder[i]) {
root.left = reConstructBinaryTree(Arrays.copyOfRange(preOrder, 1, i + 1),
Arrays.copyOfRange( inOrder, 0, i));
root.right = reConstructBinaryTree(Arrays.copyOfRange(preOrder, i + 1,
preOrder.length),
Arrays.copyOfRange( inOrder, i + 1, inOrder.length));
break;
}
}
return root;
}