BM41 题解 | #输出二叉树的右视图#
输出二叉树的右视图
https://www.nowcoder.com/practice/c9480213597e45f4807880c763ddd5f0
看见进步：
真棒，Good job! 这次是自己做出整个二叉树的最后一道题目了，都是前面所有的题目，积累的知识厚积薄发，带来的效果，真棒！真棒！真棒！棒棒棒！
解题思路：
1、用BM40的思路，重构二叉树
2、用层次遍历的方法，获得最有子节点
import java.util.*;
public class Solution {
/*
* 求二叉树的右视图
* @param preOrder int整型一维数组 先序遍历
* @param inOrder int整型一维数组 中序遍历
* @return int整型一维数组
*/
public int[] solve (int[] preOrder, int[] inOrder) {
TreeNode root = deConstructTreeNode(preOrder,inOrder);
ArrayList<Integer> res = getSloveArray(root);
int[] resArr = res.stream().mapToInt(i->i).toArray();
return resArr;
}
/**
* 层次遍历整个二叉树，获得最后一个节点
*/
public ArrayList<Integer> getSloveArray(TreeNode root) {
ArrayList<Integer> res = new ArrayList<Integer>();
if(root == null) {
return res;
}
ArrayDeque<TreeNode> q = new ArrayDeque<>();
q.offer(root);
while(!q.isEmpty()) {
int n = q.size();
for(int i=0; i<n; i++) {
TreeNode node = q.poll();
if(i== n-1) {
res.add(node.val);
}
if(node.left!=null) {
q.offer(node.left);
}
if(node.right!=null) {
q.offer(node.right);
}
}
}
return res;
}
public TreeNode deConstructTreeNode(int[] pre, int[] vin) {
int m = pre.length;
int n = vin.length;
if(m ==0 || n == 0) {
return null;
}
TreeNode root = new TreeNode(pre[0]);
for(int i=0; i<n; i++) {
if(pre[0] == vin[i]) {
root.left = deConstructTreeNode(
Arrays.copyOfRange(pre, 1, i+1),
Arrays.copyOfRange(vin, 0, i)
);
root.right = deConstructTreeNode(
Arrays.copyOfRange(pre, i+1, n),
Arrays.copyOfRange(vin, i+1, n)
);
}
}
return root;
}
}
查看14道真题和解析