314. Binary Tree Vertical Order Traversal
发布时间:2020-12-14 03:49:42 所属栏目:大数据 来源:网络整理
导读:314 . Binary Tree Vertical Order Traversal /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { class Pair{ TreeNode node; I
314. Binary Tree Vertical Order Traversal /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { class Pair{ TreeNode node; Integer pos; public Pair(TreeNode node,Integer pos){ this.node = node; this.pos = pos; } } public List<List<Integer>> verticalOrder(TreeNode root) { HashMap<Integer,List<Integer>> map = new HashMap<>(); List<List<Integer>> result = new ArrayList<>(); if(root == null){ return result; } Queue<Pair> queue = new LinkedList<>(); Integer max = 0; Integer min = 0; queue.offer(new Pair(root,0)); while(!queue.isEmpty()){ Pair cur = queue.poll(); Integer curPos = cur.pos; TreeNode curNode = cur.node; if(!map.containsKey(curPos)){ map.put(curPos,new ArrayList<>()); } map.get(curPos).add(curNode.val); if(curNode.left != null){ min = Math.min(min,curPos - 1); queue.offer(new Pair(curNode.left,curPos - 1)); } if(curNode.right != null){ max = Math.max(max,curPos + 1); queue.offer(new Pair(curNode.right,curPos + 1)); } } for(int i = min; i <= max; i++){ result.add(map.get(i)); } return result; } } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |