二叉树的右视图
题目要求
给定一个二叉树的根节点root，要求编写一个算法来模拟观察者站在树的右侧所看到的视图。具体来说，从树的顶部开始，直到底部结束，记录下每一层最右边节点的值。算法需要返回一个由这些节点值组成的列表。
解题思路
要解决这个问题，我们可以采用层次遍历（也称为广度优先搜索）的方法。层次遍历可以按照从上到下的顺序访问树中的每一层节点，并且可以容易地修改以仅记录每层最右侧的节点值。以下是解决这个问题的步骤：
- 初始化一个队列，用于存放待访问的节点，首先将根节点
root入队。 - 当队列不为空时，进行以下操作：
- 获取当前队列的长度，这个长度相当于当前层的节点数。
- 遍历当前层的所有节点：
- 对于每一层，从左到右取出节点（即队列的前端），并将其子节点（先左后右）加入队列的后端。
- 记录下当前层最后一个节点的值，因为从右侧看过去，这是该层唯一可见的节点。
- 每层遍历结束后，将最后一个节点的值加入到结果列表中。
- 当所有层都遍历完毕后，返回结果列表。
这样，我们就可以得到从二叉树的右侧看到的节点值的列表。
Golang 版本
package main
import (
"fmt"
)
// TreeNode is a structure for a binary tree node.
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
// rightSideView returns the values of the nodes you can see ordered from top to bottom.
func rightSideView(root *TreeNode) []int {
if root == nil {
return []int{}
}
result := []int{}
queue := []*TreeNode{root}
for len(queue) > 0 {
levelLength := len(queue)
for i := 0; i < levelLength; i++ {
node := queue[0]
queue = queue[1:]
// When we reach the last node of the current level, add it to the result.
if i == levelLength-1 {
result = append(result, node.Val)
}
// Add child nodes to the queue for the next level.
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
}
}
return result
}
func main() {
// Example usage:
// Construct a binary tree as an example.
// 1
// / \
// 2 3
// \ \
// 5 4
root := &TreeNode{Val: 1}
root.Left = &TreeNode{Val: 2}
root.Right = &TreeNode{Val: 3}
root.Left.Right = &TreeNode{Val: 5}
root.Right.Right = &TreeNode{Val: 4}
// Get the right side view of the binary tree.
view := rightSideView(root)
fmt.Println(view) // Output: [1 3 4]
}
这段代码定义了一个TreeNode结构体，实现了一个rightSideView函数来解决问题，并提供了一个主函数main来演示如何使用这个函数。代码中的示例二叉树与题目描述的功能相匹配，最终打印出从右侧看到的节点值。
C++版本
#include <iostream>
#include <vector>
#include <queue>
// Definition for a binary tree node.
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
std::vector<int> rightSideView(TreeNode* root) {
std::vector<int> view;
if (!root) return view;
std::queue<TreeNode*> nodesQueue;
nodesQueue.push(root);
while (!nodesQueue.empty()) {
int size = nodesQueue.size();
for (int i = 0; i < size; ++i) {
TreeNode* node = nodesQueue.front();
nodesQueue.pop();
if (i == size - 1) view.push_back(node->val);
if (node->left) nodesQueue.push(node->left);
if (node->right) nodesQueue.push(node->right);
}
}
return view;
}
};
int main() {
// Example usage:
TreeNode *root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->right = new TreeNode(5);
root->right->right = new TreeNode(4);
Solution solution;
std::vector<int> result = solution.rightSideView(root);
for (int val : result) {
std::cout << val << " ";
}
std::cout << std::endl;
// Clean up allocated nodes if necessary
delete root->left->right;
delete root->right->right;
delete root->left;
delete root->right;
delete root;
return 0;
}
这段 C++代码定义了一个TreeNode结构体和一个Solution类，其中包含了解决问题的rightSideView方法。在main函数中，我们创建了一个示例二叉树，并调用rightSideView方法来获取从右侧看到的节点值，然后打印这些值。最后，代码中还包含了适当的内存清理操作。
Python 版本
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def rightSideView(self, root: TreeNode) -> list[int]:
if not root:
return []
rightside = []
queue = [root]
while queue:
level_length = len(queue)
for i in range(level_length):
node = queue.pop(0)
# If it's the last node in the current level, add it to the rightside view
if i == level_length - 1:
rightside.append(node.val)
# Add child nodes in the queue
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return rightside
# Example usage:
if __name__ == "__main__":
# Construct a binary tree as an example.
# 1
# / \
# 2 3
# \ \
# 5 4
root = TreeNode(1, TreeNode(2, None, TreeNode(5)), TreeNode(3, None, TreeNode(4)))
# Get the right side view of the binary tree.
solution = Solution()
view = solution.rightSideView(root)
print(view) # Output: [1, 3, 4]
这段 Python 代码定义了一个TreeNode类用于表示二叉树的节点，以及一个Solution类，其中包含了解决问题的rightSideView方法。在__main__部分，我们创建了一个示例二叉树，并调用rightSideView方法来获取从右侧看到的节点值，然后打印这些值。
Java 版本
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
// Definition for a binary tree node.
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) return result;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int levelLength = queue.size();
for (int i = 0; i < levelLength; i++) {
TreeNode currentNode = queue.poll();
// If it's the last node of this level, add it to the result list
if (i == levelLength - 1) {
result.add(currentNode.val);
}
// Add left and right children of the current node to the queue
if (currentNode.left != null) {
queue.offer(currentNode.left);
}
if (currentNode.right != null) {
queue.offer(currentNode.right);
}
}
}
return result;
}
}
// Example usage
public class Main {
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.right = new TreeNode(5);
root.right.right = new TreeNode(4);
Solution solution = new Solution();
List<Integer> rightView = solution.rightSideView(root);
for (int val : rightView) {
System.out.print(val + " ");
}
}
}
这段 Java 代码定义了一个TreeNode类用于表示二叉树的节点，以及一个Solution类，其中包含了解决问题的rightSideView方法。在Main类的main方法中，我们创建了一个示例二叉树，并调用rightSideView方法来获取从右侧看到的节点值，然后打印这些值。
Rust 版本
use std::cell::RefCell; use std::rc::Rc; use std::collections::VecDeque; // Definition for a binary tree node. #[derive(Debug, PartialEq, Eq)] pub struct TreeNode { pub val: i32, pub left: Option<Rc<RefCell<TreeNode>>>, pub right: Option<Rc<RefCell<TreeNode>>>, } impl TreeNode { #[inline] pub fn new(val: i32) -> Self { TreeNode { val, left: None, right: None, } } } struct Solution; impl Solution { pub fn right_side_view(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> { let mut view = Vec::new(); if root.is_none() { return view; } let mut queue = VecDeque::new(); queue.push_back(root); while let Some(node) = queue.pop_front() { let mut level_size = queue.len(); for i in 0..level_size { if let Some(current) = queue.pop_front() { if i == level_size - 1 { // If it's the last node in the current level, add it to the view view.push(current.borrow().val); } if let Some(left) = ¤t.borrow().left { queue.push_back(Some(left.clone())); } if let Some(right) = ¤t.borrow().right { queue.push_back(Some(right.clone())); } } } // Add the next level's nodes to the queue if let Some(node) = node { if let Some(left) = node.borrow().left.clone() { queue.push_back(Some(left)); } if let Some(right) = node.borrow().right.clone() { queue.push_back(Some(right)); } } } view } } fn main() { let root = Some(Rc::new(RefCell::new(TreeNode::new(1)))); let left = Some(Rc::new(RefCell::new(TreeNode::new(2)))); let right = Some(Rc::new(RefCell::new(TreeNode::new(3)))); let left_right = Some(Rc::new(RefCell::new(TreeNode::new(5)))); let right_right = Some(Rc::new(RefCell::new(TreeNode::new(4)))); if let Some(root_node) = &root { root_node.borrow_mut().left = left; root_node.borrow_mut().right = right; } if let Some(left_node) = &root.as_ref().unwrap().borrow().left { left_node.borrow_mut().right = left_right; } if let Some(right_node) = &root.as_ref().unwrap().borrow().right { right_node.borrow_mut().right = right_right; } let view = Solution::right_side_view(root); println!("{:?}", view); // Should print [1, 3, 4] }
这段 Rust 代码定义了一个TreeNode结构体用于表示二叉树的节点，以及一个Solution结构体，其中包含了解决问题的right_side_view函数。在main函数中，我们创建了一个示例二叉树，并调用right_side_view函数来获取从右侧看到的节点值，然后打印这些值。
总结
上面的 Rust 解法实现了一个二叉树的右视图功能。这个功能通过以下步骤完成：
-
定义了一个
TreeNode结构体，用于表示二叉树的节点，每个节点包含一个整数值、一个可选的左子节点和一个可选的右子节点。 -
实现了一个
Solution结构体，其中包含了名为right_side_view的函数。这个函数接受一个Option<Rc<RefCell<TreeNode>>>类型的参数，代表二叉树的根节点。 -
在
right_side_view函数中，首先检查根节点是否为空。如果为空，则直接返回一个空的向量。 -
使用
VecDeque来实现一个队列，用于层序遍历二叉树。队列中存储的是Option<Rc<RefCell<TreeNode>>>类型的元素。 -
遍历二叉树的每一层，对于每一层的节点，只将该层最后一个节点的值添加到结果向量中。这是通过检查当前节点是否是该层的最后一个节点来实现的。
-
对于每个节点，如果它有左子节点或右子节点，就将它们添加到队列中，以便在下一次循环中遍历它们。
-
最后，函数返回包含二叉树右视图的向量。
在main函数中，创建了一个示例二叉树，并调用了Solution结构体的right_side_view函数来获取并打印从右侧看到的节点值。这个示例展示了如何使用 Rust 的Rc和RefCell来处理可变共享所有权，这在二叉树的上下文中非常有用。