LeetCode-199-二叉树的右视图

2022/4/14 23:12:52

本文主要是介绍LeetCode-199-二叉树的右视图,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

二叉树的右视图

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

示例说明请见LeetCode官网。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/binary-tree-right-side-view/
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解法一:层序遍历二叉树

利用队列先进先出的特点层序遍历二叉树,具体处理过程如下:

  • 初始化一个队列,并将根节点添加到队列中,作为第一层;
  • 循环遍历队列中每一层的元素,并暂存到二维List中,并将下一层的节点按从左到右的顺序加入到队列中;
  • 直到队列为空,遍历结束。

最后,按顺序从二维List中取每一层的最后一个元素,并返回。

import com.kaesar.leetcode.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class LeetCode_199 {
    /**
     * 层序遍历
     * 通过使用队列先进先出的方式遍历二叉树
     *
     * @param root
     * @return
     */
    public static List<Integer> rightSideView(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        // 暂存每一层的节点
        List<List<Integer>> numsList = new ArrayList<>();
        Queue<TreeNode> nodes = new LinkedList<>();
        nodes.add(root);
        // 遍历每一层的节点,并将下一层的节点按从左到右的顺序加入到队列中
        while (!nodes.isEmpty()) {
            List<Integer> nums = new ArrayList<>();
            int count = nodes.size();
            for (int i = 0; i < count; i++) {
                TreeNode cur = nodes.poll();
                nums.add(cur.val);
                if (cur.left != null) {
                    nodes.add(cur.left);
                }
                if (cur.right != null) {
                    nodes.add(cur.right);
                }
            }
            numsList.add(nums);
        }

        List<Integer> result = new ArrayList<>();
        // 按顺序取每一层的最后一个元素
        for (List<Integer> integers : numsList) {
            result.add(integers.get(integers.size() - 1));
        }
        return result;
    }

    public static void main(String[] args) {
        /**
         * 测试用例:
         *     1
         *   2   3
         *    5   4
         */
        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);

        // 期望输出: 1,3,4
        for (Integer integer : rightSideView(root)) {
            System.out.print(integer + " ");
        }
    }
}

【每日寄语】 如果一个人努力寻求向上,做好自己的工作,为自己寻找幸福,是好胜的话那么我就好胜!



这篇关于LeetCode-199-二叉树的右视图的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程