NC136- 输出二叉树的右视图

题目链接

描述

请根据二叉树的前序遍历，中序遍历恢复二叉树，并打印出二叉树的右视图

数据范围：

二叉树每个节点的值在区间[1,10000]内，且保证每个节点的值互不相同。

方法一：递归重建树+树的层次遍历（BFS）

解题思路：

这题应该分为两步完成

1. 通过前序和中序完成二叉树的重建，我们每次找到一个先序数组的第一个元素（该元素为当前树根节点）然后在中序数组中找到该节点则其左边的节点为其左子树，右边的所有节点为右子树，然后不断对字数进行同样操作，这里我们用递归完成。
2. 对第一步得到的树从根节点进行层次遍历（也可以说BFS）每次遍历一层确定每一层有多少个节点然后把最后一个节点拿出来即可。

图解

代码

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     * @param xianxu int整型一维数组 先序遍历
     * @param zhongxu int整型一维数组 中序遍历
     * @return int整型一维数组
     */
    class TreeNode {    // 树的节点
        int val;
        TreeNode left = null;    // 左右子树
        TreeNode right = null;
        TreeNode() {
        }
        TreeNode(int x) {
            val = x;
        }
}

    public int[] solve (int[] xianxu, int[] zhongxu) {
        // write code heretemp
        if(xianxu.length == 0){        // 空树直接返回
            return (new int[0]);
        }
        Vector<Integer> temp = new Vector<Integer>();    // 记录答案直接返回
        TreeNode tree = getTree(xianxu, 0, xianxu.length - 1, zhongxu, 0, zhongxu.length - 1);        // 递归重建树
        Queue<TreeNode> queue = new LinkedList<TreeNode>();        // 层次遍历存节点
        queue.offer(tree);        
        int sum = 1;    // 记录每层多少个节点
        while(!queue.isEmpty()){
            for(int i = 1; i <= sum; ++i){
                if(queue.element().left != null){    // 左子树不为空则加入队列
                    queue.add(queue.element().left);
                }
                if(queue.element().right != null){    // 右子树不为空则加入队列
                    queue.add(queue.element().right);
                }
                if(i == sum){        // 当前是该层最后一个节点
                    temp.add(queue.element().val);
                }
                queue.remove();         
            }
            sum = queue.size();        // 更新该层节点个数
        }
        int[] res = new int[temp.size()];    // 返回数组，这题竟然用int[]返回,太坑了（小声逼逼）。
        for(int i = 0; i < temp.size(); ++i){
            res[i] = temp.get(i);
        }
        return res;
    }

    public TreeNode getTree(int[] xian, int x_l, int x_r, int[] zhong, int z_l, int z_r){
        TreeNode res = new TreeNode(xian[x_l]);        // 先序的第一个节点一定是根节点
        int fu = z_l - 1;    // 我们在中序数组中找根节点
        while(zhong[++fu] != xian[x_l]);
        if(fu > z_l){    // 如果有左子树
            res.left = getTree(xian, x_l + 1, x_l + fu - z_l, zhong, z_l, fu - 1);    // 注意左右子树在先序和后序数组中的范围
        }
        if(fu < z_r){    // 如果有右子树
            res.right = getTree(xian, x_l + fu - z_l + 1, x_r, zhong, fu + 1, z_r);
        }
        return res;        // 返回树的根节点
    }
}

复杂度分析

• 时间复杂度递归时每个点确定一次位置然后层次遍历每个点确定是不是最右边的节点。

• 空间复杂度每个节点一个TreeNode节点，然后一个res数组返回结果。

（原谅我的愚笨，并没有想出第二种方法）