leetcode [199]Binary Tree Right Side View

佚名 7年前 (2019-04-24) 随笔 844人围观抢沙发百度已收录

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.

Example:

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

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

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

题目大意：

给出一颗二叉树，从右向左看得到的树节点值的集合。

解法：

其实就是层序遍历后的，每一层的最后一个节点的集合，我是采用非迭代层序遍历做的。

java:

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer>res=new ArrayList<Integer>();
        if(root==null) return res;
        Deque<TreeNode>q=new LinkedList<TreeNode>();
        q.push(root);
        while(!q.isEmpty()){
            int n=q.size();
            for(int i=0;i<n;i++){
                TreeNode tmp=q.pollFirst();
                if(i==n-1) res.add(tmp.val);
                if(tmp.left!=null) q.addLast(tmp.left);
                if(tmp.right!=null) q.addLast(tmp.right);
            }
        }
        return res;
    }
}

还可以使用迭代的层次遍历进行改进,代码更加简洁。

java:

class Solution {
    public void helper(TreeNode root,int curSize,List<Integer>res){
        if(root==null) return;
        
        if(curSize==res.size()) res.add(root.val);
        
        helper(root.right,curSize+1,res);
        helper(root.left,curSize+1,res);
    }

    public List<Integer> rightSideView(TreeNode root) {
        List<Integer>res=new ArrayList<Integer>();
        helper(root,0,res);
        
        return res;
    }
}