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) {
boolean flag=true;
List<Integer> list=new ArrayList<>();
ArrayList<TreeNode> res=new ArrayList<TreeNode>();
Map<Integer,Integer> map=new HashMap<>(); if(root==null)
return list; res=LevelTraverse(root);
list.add(root.val);
map.put(0,0); while(flag)
{
while(root.right!=null)
{
root=root.right;
list.add(root.val);
map.put(res.indexOf(root),res.indexOf(root)); }
if(root.left!=null)
{
root=root.left;
list.add(root.val);
map.put(res.indexOf(root),res.indexOf(root));
}
else{
if(res.indexOf(root)-1<0)
flag=false;
else {
root=res.get(res.indexOf(root)-1);
if(map.containsKey(res.indexOf(root)))
break;
}
}
}
return list;
} public ArrayList<TreeNode> LevelTraverse(TreeNode root)//树的水平遍历
{
ArrayList<TreeNode> list=new ArrayList<TreeNode>();
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
while(queue.size()>0)
{
TreeNode a=(TreeNode)queue.peek();
queue.remove();
list.add(a);
if(a.left!=null)
queue.add(a.left);
if(a.right!=null)
queue.add(a.right);
} return list;
}
}