导航：首页 > 互联网科技 >

如何解析python二叉树的右视图

发表于：2025-01-23 作者：千家信息网编辑

千家信息网最后更新 2025年01月23日，本篇文章为大家展示了如何解析python二叉树的右视图，内容简明扼要并且容易理解，绝对能使你眼前一亮，通过这篇文章的详细介绍希望你能有所收获。给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺

千家信息网最后更新 2025年01月23日如何解析python二叉树的右视图

本篇文章为大家展示了如何解析python二叉树的右视图，内容简明扼要并且容易理解，绝对能使你眼前一亮，通过这篇文章的详细介绍希望你能有所收获。

给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例:

输入: [1,2,3,null,5,null,4] 输出: [1, 3, 4] 解释: 1 <--- / \ 2 3 <--- \ \ 5 4 <---

答案：

 1public List rightSideView(TreeNode root) {
 2    if (root == null)
 3        return new ArrayList();
 4    Queue queue = new LinkedList();
 5    queue.offer(root);
 6    List res = new ArrayList();
 7    while (!queue.isEmpty()) {
 8        int size = queue.size();
 9        while (size-- > 0) {
10            TreeNode cur = queue.poll();
11            if (size == 0)
12                res.add(cur.val);
13            if (cur.left != null)
14                queue.offer(cur.left);
15            if (cur.right != null)
16                queue.offer(cur.right);
17        }
18    }
19    return res;
20}

解析：

原理很简单，我们通过bfs（广度优先搜索）遍历每一行，然后记录一下每一行的最右的那个节点即可。在看一种递归的解法

 1public List rightSideView(TreeNode root) {
 2    List result = new ArrayList();
 3    rightView(root, result, 0);
 4    return result;
 5}
 6
 7public void rightView(TreeNode curr, List result, int currDepth) {
 8    if (curr == null) {
 9        return;
10    }
11    if (currDepth == result.size()) {
12        result.add(curr.val);
13    }
14    rightView(curr.right, result, currDepth + 1);
15    rightView(curr.left, result, currDepth + 1);
16}