Java Level order traversal, easy to understand


  • 0
    A

    Level order traversal, using a new class Pair to record the level of each node

       public class Solution {
            public List<List<Integer>> verticalOrder(TreeNode root) {
                List<List<Integer>> results = new ArrayList<>();
                if(root == null){
                    return results;
                }
                HashMap<Integer, List<Integer>> vLevelMap = new HashMap<>();
                List<Pair> hLevel = new ArrayList<>();
                hLevel.add(new Pair(root, 0));
                int min = 0;
                int max = 0;
                while(!hLevel.isEmpty()){
                    List<Pair> hParent = hLevel;
                    hLevel = new ArrayList<>();
                    for(Pair p : hParent){
                        if(vLevelMap.get(p.level) == null){
                            vLevelMap.put(p.level, new ArrayList<>());
                        }
                        vLevelMap.get(p.level).add(p.node.val);
                        if(p.node.left != null){
                            hLevel.add(new Pair(p.node.left, p.level - 1));
                            min = min < p.level - 1 ? min : p.level - 1;
                        }
                        if(p.node.right != null){
                            hLevel.add(new Pair(p.node.right, p.level + 1));
                            max = max > p.level + 1 ? max : p.level + 1;
                        }
                    }
                }
                for(int i = min; i <= max; ++i){
                    results.add(vLevelMap.get(i));
                }
                return results;
            }
            
            private class Pair{
                TreeNode node;
                int level;
                
                Pair(TreeNode node, int level){
                    this.node = node;
                    this.level = level;
                }
            }
        }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.