题解 | #NC136 输出二叉树的右视图#

输出二叉树的右视图

http://www.nowcoder.com/practice/c9480213597e45f4807880c763ddd5f0

先构造二叉树,再使用层序遍历取最右侧节点

import java.util.*;

// 构造节点
class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     * 求二叉树的右视图
     * @param xianxu int整型一维数组 先序遍历
     * @param zhongxu int整型一维数组 中序遍历
     * @return int整型一维数组
     */

    private HashMap<Integer, Integer> map = new HashMap<>();
    ArrayList<Integer> list = new ArrayList<>();

    public int[] solve (int[] qianxu, int[] zhongxu) {
        // write code here
        for (int i = 0; i < zhongxu.length; i++) map.put(zhongxu[i], i);
        TreeNode root = build(qianxu, 0, qianxu.length - 1, 0, zhongxu.length - 1);
        rightView(root);
        int[] res = new int[list.size()];
        for (int i = 0; i < res.length; i++) res[i] = list.get(i);
        return res;
    }

    // 构造二叉树
    public TreeNode build(int[] qianxu, int ps, int pe, int is, int ie) {
        if (ps > pe || is > ie) return null;
        int val = qianxu[ps];
        int id = map.get(val);
        TreeNode root = new TreeNode(val);
        root.left = build(qianxu, ps + 1, ps + id - is, is, id - 1);
        root.right = build(qianxu, ps + id - is + 1, pe, id + 1, ie);
        return root;
    }

    // 层序遍历取最右侧节点
    public void rightView(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        if (root != null) queue.offer(root);
        while (!queue.isEmpty()) {
            int n = queue.size();
            for (int i = 0; i < n; i++) {
                TreeNode node = queue.poll();
                if (i == n - 1) list.add(node.val);
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
        }
    }
}
全部评论

相关推荐

06-07 19:59
门头沟学院 C++
补药卡我啊😭:都快15年前的了还在11新特性
你的简历改到第几版了
点赞 评论 收藏
分享
湫湫湫不会java:1.在校经历全删了2.。这些荣誉其实也没啥用只能说,要的是好的开发者不是好好学生3.项目五六点就行了,一个亮点一俩行,xxx技术解决,xxx问题带来xxx提升。第一页学历不行,然后啥有价值的信息也没有,到第二页看到项目了,第一个项目九点,第二个项目像凑数的俩点。总体给人又臭又长,一起加油吧兄弟
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务