首页 > 其他 > 详细

199. Binary Tree Right Side View

时间:2018-10-18 21:43:27      阅读:157      评论:0      收藏:0      [点我收藏+]

一、题目

  1、审题

   技术分享图片

  2、分析

    一棵二叉树,从右边看他,看到的每一层的第一个元素存起来。

 

二、解答

  1、思路:

    方法一、

    采用 Queue 进行层次遍历,且每次获取一层的最右边一个元素。

    public List<Integer> rightSideView(TreeNode root) {
        
        if(root == null)
            return null;
        List<Integer> result = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            
            int size = queue.size();
            for (int i = 0; i < size; i++) {

                TreeNode node = queue.poll();
                if(i == 0) {
                    result.add(node.val); 
                }
                if(node.right != null)
                    queue.add(node.right);
                if(node.left != null)
                    queue.add(node.left);
            }
            
                
        }
        return result;
    }

 

  方法二、

    采用递归获取每一层最右边元素;

    即修改后的前序遍历,遍历顺序为: 根 --> 右 --> 左 ;

    巧妙的将所遍历到的层次与 List 中元素的个数进行关联起来。

    public List<Integer> rightSideView2(TreeNode root) {
        
        List<Integer> result = new ArrayList<>();
        rightView(root, result, 0);
        return result;
    }
    
    private void rightView(TreeNode root, List<Integer> result, int curDepth) {
        
        if(root == null)
            return;
        
        if(curDepth == result.size())
            result.add(root.val);
        
        rightView(root.right, result, curDepth + 1);
        rightView(root.left, result, curDepth + 1);
    }

 

199. Binary Tree Right Side View

原文:https://www.cnblogs.com/skillking/p/9813028.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!