首页 > itarticle > [leetcode]binary tree right side view

[leetcode]binary tree right side view

admin 11月 11, 2020 0

题目描述

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.

For example:
Given the following binary tree,

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

You should return [1, 3, 4].

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        rightView(root, res, 0);
        return res;
    }
    //一层就取一个，而且是最右边
    public void rightView(TreeNode root, List<Integer> res, int currHeight){
        if(root == null) return;
        
        //tricky，因为一层就取一个（最右边的），当res.size()==currHeight时，说明该元素就是该层最右边的元素
        if(res.size() == currHeight) res.add(root.val);
        
        //右边优先
        rightView(root.right, res, currHeight+1);
        rightView(root.left, res, currHeight+1);
        
    }
}