你的位置:首页 > Java教程

[Java教程]199. Binary Tree Right Side View


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].

代码如下:

 1 /** 2  * Definition for a binary tree node. 3  * public class TreeNode { 4  *   int val; 5  *   TreeNode left; 6  *   TreeNode right; 7  *   TreeNode(int x) { val = x; } 8  * } 9 */10 public class Solution {11   public List<Integer> rightSideView(TreeNode root) {12     boolean flag=true;13     List<Integer> list=new ArrayList<>();14     ArrayList<TreeNode> res=new ArrayList<TreeNode>();15     Map<Integer,Integer> map=new HashMap<>();16     17     if(root==null)18     return list;19 20     res=LevelTraverse(root);21      list.add(root.val);22     map.put(0,0);23     24     while(flag)25     {26    while(root.right!=null)27     {28      root=root.right;29       list.add(root.val);30       map.put(res.indexOf(root),res.indexOf(root));31 32     }33     if(root.left!=null)34     {35      root=root.left;36       list.add(root.val);37       map.put(res.indexOf(root),res.indexOf(root));38     }39    else{40       if(res.indexOf(root)-1<0)41       flag=false;42       else {43         root=res.get(res.indexOf(root)-1);44         if(map.containsKey(res.indexOf(root)))45         break;46       }47     }48     }49     return list;50   }51   52   public ArrayList<TreeNode> LevelTraverse(TreeNode root)//树的水平遍历53   {54     ArrayList<TreeNode> list=new ArrayList<TreeNode>();55     Queue<TreeNode> queue = new LinkedList<TreeNode>();56     queue.add(root);57     while(queue.size()>0)58     {59       TreeNode a=(TreeNode)queue.peek();60       queue.remove();61       list.add(a);62       if(a.left!=null)63       queue.add(a.left);64       if(a.right!=null)65       queue.add(a.right);66     }67  68     return list;69   }70 }