你的位置:首页 > Java教程

[Java教程]Leetcode: 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].

这道题就是BT的Level Order Traversal,每次要换一层的时候,记录当前节点

 1 /** 2  * Definition for binary tree 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     ArrayList<Integer> res = new ArrayList<Integer>();13     if (root == null) return res;14     LinkedList<TreeNode> queue = new LinkedList<TreeNode>();15     queue.offer(root);16     int PNum = 1;17     int CNum = 0;18     while (!queue.isEmpty()) {19       TreeNode cur = queue.poll();20       PNum--;21       if (cur.left != null) {22         queue.offer(cur.left);23         CNum++;24       }25       if (cur.right != null) {26         queue.offer(cur.right);27         CNum++;28       }29       if (PNum == 0) {30         res.add(cur.val);31         PNum = CNum;32         CNum = 0;33       }34     }35     return res;36   }37 }