README.md

剑指 Offer II 046. 二叉树的右侧视图

题目描述

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

 

示例 1:

输入: [1,2,3,null,5,null,4]
输出: [1,3,4]

示例 2:

输入: [1,null,3]
输出: [1,3]

示例 3:

输入: []
输出: []

 

提示:

• 二叉树的节点个数的范围是 [0,100]
• -100 <= Node.val <= 100 

 

注意：本题与主站 199 题相同：https://leetcode-cn.com/problems/binary-tree-right-side-view/

解法

层序遍历，取每层最后一个元素

Python3

# Definition for a binary tree node.
# 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]:
        ans = []
        if not root:
            return ans
        d = deque([root])
        while d:
            n = len(d)
            for i in range(n):
                node = d.popleft()
                if i == n - 1:
                    ans.append(node.val)
                if node.left:
                    d.append(node.left)
                if node.right:
                    d.append(node.right)
        return ans

Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        Queue<TreeNode> q = new ArrayDeque<>();
        q.offer(root);
        while (!q.isEmpty()) {
            int n = q.size();
            for (int i = 0; i < n; i++) {
                TreeNode node = q.poll();
                if (i == n - 1) {
                    ans.add(node.val);
                }
                if (node.left != null) {
                    q.offer(node.left);
                }
                if (node.right != null) {
                    q.offer(node.right);
                }
            }
        }
        return ans;
    }
}

C++

class Solution
{
public:
    vector<int> rightSideView ( TreeNode* root )
    {
        vector<int> res;

        if ( !root )
        {
            return res;
        }

        queue<TreeNode* > que;
        que.push ( root );

        while ( !que.empty() )
        {
            int size = que.size();

            for ( int i = 0; i < size; i++ )
            {
                TreeNode* ptr = que.front();
                que.pop();

                if ( i == size - 1 )
                {
                    res.push_back ( ptr->val );
                }

                if ( ptr->left )
                {
                    que.push ( ptr->left );
                }

                if ( ptr-> right )
                {
                    que.push ( ptr->right );
                }
            }
        }

        return res;
    }
};

Go

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func rightSideView(root *TreeNode) []int {
    var ans []int
    if root == nil {
        return ans
    }
    q := []*TreeNode{root}
    for n := len(q); n > 0; n = len(q) {
        for i := 0; i < n; i++ {
            node := q[0]
            q = q[1:]
            if i == n - 1 {
                ans = append(ans, node.Val)
            }
            if node.Left != nil {
                q = append(q, node.Left)
            }
            if node.Right != nil {
                q = append(q, node.Right)
            }
        }
    }
    return ans
}

...