二叉树的右视图( LeetCode 199 )

一、题目描述

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

二、题目解析

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 二叉树的右视图( LeetCode 199 ): https://leetcode-cn.com/problems/binary-tree-right-side-view/
class Solution {
    public List<Integer> rightSideView(TreeNode root) {

        // 设置一个数组用来存储二叉树的右视图结果
        // 题目要求存储的是节点的值,所以类型是 Integer
        List<Integer> list = new LinkedList<>();

        // 设置一个队列,用来保存二叉树每一层的节点
        Queue<TreeNode> que = new LinkedList<>();

        // 边界判断
        if (root == null) return list;

        // 首先,把二叉树的根节点加入到队列中
        que.add(root);

        // 观察队列是否为空
        while (!que.isEmpty()) {

            // 1、获取队列的长度
            int levelSize = que.size();

            // 2、通过一个循环,获取队列中每个节点的左右子树,把这些左右子树节点也添加到队列中
            for (int i = 0; i < levelSize; i++) {

                // 3、弹出队列的队首元素
                TreeNode node = que.poll();

                // 4、判断弹出的节点是否有左子树
                if (node.left != null) {
                    // 如果有左子树,把它加入到队列中
                    que.add(node.left);
                }

                // 5、判断弹出的节点是否有右子树
                if (node.right != null) {
                    // 如果有右子树,把它加入到队列中
                    que.add(node.right);
                }

                // 对于每一层的二叉树节点,我们是从左到右依次添加,所以末尾的节点的顺序是 levelSize - 1
                // 6、这个末尾的节点就是这一层中最右侧的节点 
                if (i == levelSize - 1) {
                    // 把最右侧的节点值加入到结果中
                    list.add(node.val);
                }
            }
        }
        // 返回结果
        return list;
    }
}

2、C++ 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 二叉树的右视图( LeetCode 199 ): https://leetcode-cn.com/problems/binary-tree-right-side-view/
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {

        // 设置一个数组用来存储二叉树的右视图结果
        // 题目要求存储的是节点的值,所以类型是 Integer
        vector<int> list;

        // 设置一个队列,用来保存二叉树每一层的节点
        queue<TreeNode*> que;

        // 边界判断
        if (root == NULL) return list;

        // 首先,把二叉树的根节点加入到队列中
        que.push(root);

        // 观察队列是否为空
        while (!que.empty()) {

            // 1、获取队列的长度
            int levelSize = que.size();

            // 2、通过一个循环,获取队列中每个节点的左右子树,把这些左右子树节点也添加到队列中
            for (int i = 0; i < levelSize; i++) {

                // 3、弹出队列的队首元素
                TreeNode* node = que.front();
                que.pop();

                // 4、判断弹出的节点是否有左子树
                if (node->left != NULL) {
                    // 如果有左子树,把它加入到队列中
                    que.push(node->left);
                }

                // 5、判断弹出的节点是否有右子树
                if (node->right != NULL) {
                    // 如果有右子树,把它加入到队列中
                    que.push(node->right);
                }

                // 对于每一层的二叉树节点,我们是从左到右依次添加,所以末尾的节点的顺序是 levelSize - 1
                // 6、这个末尾的节点就是这一层中最右侧的节点 
                if (i == levelSize - 1) {
                    // 把最右侧的节点值加入到结果中
                    list.push_back(node->val);
                }
            }
        }
        // 返回结果
        return list;

    }
};

3、Python 代码

# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者:程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 二叉树的右视图( LeetCode 199 ): https://leetcode-cn.com/problems/binary-tree-right-side-view/
class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:

        # 设置一个数组用来存储二叉树的右视图结果
        # 题目要求存储的是节点的值,所以类型是 Integer
        list = []

        # 设置一个队列,用来保存二叉树每一层的节点
        que = deque()

        # 边界判断
        if not root :
           return list

        # 首先,把二叉树的根节点加入到队列中
        que.append(root)

        # 观察队列是否为空
        while que:

            # 1、获取队列的长度
            levelSize = len(que)

            # 2、通过一个循环,获取队列中每个节点的左右子树,把这些左右子树节点也添加到队列中
            for i in range(levelSize):

                # 3、弹出队列的队首元素
                node = que.popleft()

                # 4、判断弹出的节点是否有左子树
                if node.left :
                    # 如果有左子树,把它加入到队列中
                    que.append(node.left)


                # 5、判断弹出的节点是否有右子树
                if node.right :
                    # 如果有右子树,把它加入到队列中
                    que.append(node.right)


                # 对于每一层的二叉树节点,我们是从左到右依次添加,所以末尾的节点的顺序是 levelSize - 1
                # 6、这个末尾的节点就是这一层中最右侧的节点 
                if i == levelSize - 1 :
                    # 把最右侧的节点值加入到结果中
                    list.append(node.val)

        # 返回结果
        return list

四、动画理解(没有声音)

发表评论

邮箱地址不会被公开。 必填项已用*标注