描述
请根据二叉树的前序遍历，中序遍历恢复二叉树，并打印出二叉树的右视图
示例1
输入：
[1,2,4,5,3],[4,2,5,1,3]
复制
返回值：
[1,3,5]
复制
备注：
二叉树每个节点的值在区间[1,10000]内，且保证每个节点的值互不相同。
方法一
思路
- 二叉树，深度优先遍历
- 先序遍历：
- 中序遍历：
- 故先序遍历输出序列中第一个节点必为根节点，且在中序遍历输出序列中根节点左右两端的序列分比为其左右子树的中序遍历。
- 假设先序遍历输出序列为数组pre，中序遍历输出序列为in，pre[0]在in中的位置为index，则其左子树的先序遍历输出序列以及中序遍历输出序列分别为
，右子树的先序遍历输出序列以及中序遍历输出序列分别为
。
- 故可以递归遍历整个数组，生成整个二叉树。参考下图示例：
- 二叉树生成后，可以通过深度优先遍历找出右视图的所有节点，需要注意的是这里的深度优先遍历是用右子节点开始的，也就是先从右边开始深度优先遍历，这样每一层第一个遍历到的节点即为右视图节点集合中的一员，参考下图示例：
- 代码如下：
import java.util.*;
public class Solution {
// 二叉树节点类
class Node{
int val;
Node left;
Node right;
// 每个节点深度
int height = 0;
public Node(int val){
this.val = val;
}
}
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 求二叉树的右视图
* @param xianxu int整型一维数组 先序遍历
* @param zhongxu int整型一维数组 中序遍历
* @return int整型一维数组
*/
public int[] solve (int[] xianxu, int[] zhongxu) {
// 根据中序和先序遍历生成二叉树
Node root = generateTree(xianxu,zhongxu);
List<Integer> res = new ArrayList<>();
Stack<Node> stack = new Stack<>();
int height = 0;
stack.add(root);
// 从右边进行深度优先遍历
while(!stack.isEmpty()){
Node node = stack.pop();
if (node.height == height){
res.add(node.val);
++height;
}
if (node.left != null){
node.left.height = node.height + 1;
stack.add(node.left);
}
if (node.right != null){
node.right.height = node.height + 1;
stack.add(node.right);
}
}
int[] ans = new int[res.size()];
for (int i = 0;i < res.size();++i){
ans[i] = res.get(i);
}
return ans;
}
private Node generateTree(int[] preorder,int[] infixorder){
// 空，返空
if (preorder == null || infixorder == null ||
preorder.length == 0){
return null;
}
// 单个元素，直接返回该节点
if (preorder.length == 1){
return new Node(preorder[0]);
}
// 依据先序遍历的第一个点，分割中序遍历的数组
int n = 0;
for(int i = 0;i < infixorder.length;++i){
if (infixorder[i] == preorder[0]){
n = i;
break;
}
}
int[] p1 = new int[n];
int[] p2 = new int[preorder.length-n-1];
int[] i1 = new int[n];
int[] i2 = new int[p2.length];
// 左子树的前序以及中序遍历
for (int i = 0;i < n;++i){
p1[i] = preorder[i+1];
i1[i] = infixorder[i];
}
// 右子树的前序以及中序遍历
for (int i = 0;i < p2.length;++i){
p2[i] = preorder[i+n+1];
i2[i] = infixorder[i+n+1];
}
Node root = new Node(preorder[0]);
root.left = generateTree(p1,i1);
root.right = generateTree(p2,i2);
return root;
}
}- 时间复杂度：
，递归生成二叉树最坏情况下的时间复杂度是
，故其时间复杂度为
- 空间复杂度：
方法二
思路
- 方法一是通过递归生成原二叉树，再遍历二叉树从而找到所有的右视图节点集合。
- 实际上可以不生成原二叉树，而是在递归的过程中就将所有的右视图节点找出。
- 首先生成原二叉树的过程实际上就是遍历每一棵子树的过程，每往下递归一次，就是遍历更深的子树，那么我们先遍历右子树也就是中序遍历中的根节点右边的序列，若右子树序列不为空，则其根节点必然是右视图中的集合，直接将根节点放入右视图节点集合，继续往下遍历即可；若右子树序列为空，就遍历左子树，此时没有右子树，那左子树的根节点必然是右视图所见到的第二层节点，继续往下遍历即可。
- 方法一中频繁创建子树的先序和中序输出序列，造成了很大的空间浪费，可以转换成使用下标来表示每个子数组的先序和中序输出序列，从而降低使用空间。
- 代码如下：
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 求二叉树的右视图
* @param xianxu int整型一维数组 先序遍历
* @param zhongxu int整型一维数组 中序遍历
* @return int整型一维数组
*/
private List<Integer> res = new ArrayList<>();
private Map<Integer,Integer> map = new HashMap<>();
private int[] preorder = null;
private int[] infixorder = null;
public int[] solve (int[] xianxu, int[] zhongxu) {
for(int i = 0;i < zhongxu.length;++i){
map.put(zhongxu[i],i);
}
this.preorder = xianxu;
this.infixorder = zhongxu;
// 深度优先遍历
searchRightestNode(0,xianxu.length-1,0,zhongxu.length-1,0);
int[] ans = new int[res.size()];
// 将列表转换成数组
for(int i = 0;i < res.size();++i){
ans[i] = res.get(i);
}
return ans;
}
// 递归找出右视图中的所有节点
private void searchRightestNode(int s1,
int e1,int s2,int e2,int height){
// 空，返回
if (s1 > e1){
return;
}
// 根节点
int root = preorder[s1];
// 当前高度的右视图节点暂时没找到，
// 则直接将root放入右视图节点集合中
if (res.size() <= height){
res.add(root);
}
// 分割点
int i = map.get(root);
// 先遍历右边的节点
searchRightestNode(s1 + i - s2 + 1,e1,i + 1,e2,height+1);
// 后遍历左边的节点
searchRightestNode(s1 + 1,s1 + i - s2,s2,i - 1,height+1);
}
}- 时间复杂度：
- 空间复杂度：
京公网安备 11010502036488号