[LeetCode] 199. Binary Tree Right Side View 二叉树的右侧视图

2021年09月15日 阅读数:1
这篇文章主要向大家介绍[LeetCode] 199. Binary Tree Right Side View 二叉树的右侧视图,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.html


Input: [1,2,3,null,5,null,4]
Output: [1, 3, 4]

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---
解法2:  BFS
public class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        rightView(root, result, 0);
        return result;
    public void rightView(TreeNode curr, List<Integer> result, int currDepth){
        if(curr == null){
        if(currDepth == result.size()){
        rightView(curr.right, result, currDepth + 1);
        rightView(curr.left, result, currDepth + 1);

Python: DFS node

# Time:  O(n)
# Space: O(h)
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):
    # @param root, a tree node
    # @return a list of integers
    def rightSideView(self, root):
        result = []
        self.rightSideViewDFS(root, 1, result)
        return result

    def rightSideViewDFS(self, node, depth, result):
        if not node:

        if depth > len(result):

        self.rightSideViewDFS(node.right, depth+1, result)
        self.rightSideViewDFS(node.left, depth+1, result)

Python: BFS  python

# Time:  O(n)
# Space: O(n)
class Solution2(object):
    # @param root, a tree node
    # @return a list of integers
    def rightSideView(self, root):
        if root is None:
            return []

        result, current = [], [root]
        while current:
            next_level = []
            for node in current:
                if node.left:
                if node.right:
            current = next_level

        return result

Python: Compute the right view of both right and left left subtree, then combine them. For very unbalanced trees, this can be O(n^2), though.app

def rightSideView(self, root):
    if not root:
        return []
    right = self.rightSideView(root.right)
    left = self.rightSideView(root.left)
    return [root.val] + right + left[len(right):]

Python: DFS-traverse the tree right-to-left, add values to the view whenever we first reach a new record depth. This is O(n).ide

def rightSideView(self, root):
    def collect(node, depth):
        if node:
            if depth == len(view):
            collect(node.right, depth+1)
            collect(node.left, depth+1)
    view = []
    collect(root, 0)
    return view 

Python: Traverse the tree level by level and add the last value of each level to the view. This is O(n).post

def rightSideView(self, root):
    view = []
    if root:
        level = [root]
        while level:
            view += level[-1].val,
            level = [kid for node in level for kid in (node.left, node.right) if kid]
    return view  

C++: DFSthis

class Solution {
    void recursion(TreeNode *root, int level, vector<int> &res)
        if(root==NULL) return ;
        if(res.size()<level) res.push_back(root->val);
        recursion(root->right, level+1, res);
        recursion(root->left, level+1, res);
    vector<int> rightSideView(TreeNode *root) {
        vector<int> res;
        recursion(root, 1, res);
        return res;

C++: BFS url

class Solution {
    vector<int> rightSideView(TreeNode *root) {
        vector<int> res;
        if (!root) return res;
        queue<TreeNode*> q;
        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; ++i) {
                TreeNode *node = q.front();
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
        return res;




[LeetCode] 102. Binary Tree Level Order Traversal 二叉树层序遍历

[LeetCode] 107. Binary Tree Level Order Traversal II 二叉树层序遍历 II


All LeetCode Questions List 题目汇总