LeetCode 314 - Binary Tree Vertical Order Traversal


https://leetcode.com/problems/vertical-order-traversal-of-a-binary-tree/
http://www.cnblogs.com/EdwardLiu/p/5093131.html
Given a binary tree, return the vertical order traversal of its nodes' values. (ie, from top to bottom, column by column).
If two nodes are in the same row and column, the order should be from left to right.
Given binary tree [3,9,20,4,5,2,7],
    _3_
   /   \
  9    20
 / \   / \
4   5 2   7
return its vertical order traversal as:
[
  [4],
  [9],
  [3,5,2],
  [20],
  [7]
]

X. Level Order Traversal
https://github.com/mintycc/OnlineJudge-Solutions/blob/master/Leetcode/314_Binary_Tree_Vertical_Order_Traversal.java
    private class QueueNode {
        public TreeNode node;
        public int depth;
        public QueueNode(TreeNode node, int depth) {
            this.node = node;
            this.depth = depth;
        }
    }
    
    public List<List<Integer>> verticalOrder(TreeNode root) {
        if (root == null) return Collections.emptyList();
        
        Queue<QueueNode> queue = new LinkedList<>();
        Map<Integer, List<Integer>> map = new HashMap<>();
        queue.add(new QueueNode(root, 0));
        
        int min = 0, max = 0;
        while (!queue.isEmpty()) {
            TreeNode cur = queue.peek().node;
            int depth = queue.poll().depth;
            if (!map.containsKey(depth)) 
                map.put(depth, new ArrayList<>());
            map.get(depth).add(cur.val);
            min = Math.min(min, depth);
            max = Math.max(max, depth);
            
            if (cur.left  != null)
                queue.add(new QueueNode(cur.left,  depth - 1));
            if (cur.right != null)
                queue.add(new QueueNode(cur.right, depth + 1));
        }
        
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = min; i <= max; i ++)
            ans.add(map.get(i));
        return ans;
    }

https://www.geeksforgeeks.org/print-a-binary-tree-in-vertical-order-set-3-using-level-order-traversal/
If we use level order traversal, we can make sure that if a node like 12 comes below in same vertical line, it is printed after a node like 9 which comes above in vertical line.
1. To maintain a hash for the branch of each node.
2. Traverse the tree in level order fashion.
3. In level order traversal, maintain a queue
   which holds, node and its vertical branch.
    * pop from queue.
    * add this node's data in vector corresponding
      to its branch in the hash.
    * if this node hash left child, insert in the 
      queue, left with branch - 1.
    * if this node hash right child, insert in the 
      queue, right with branch + 1
https://discuss.leetcode.com/topic/31954/5ms-java-clean-solution
The following solution takes 5ms.
  • BFS, put node, col into queue at the same time
  • Every left child access col - 1 while right child col + 1
  • This maps node into different col buckets
  • Get col boundary min and max on the fly
  • Retrieve result from cols
Note that TreeMap version takes 9ms.
Here is an example of [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]. Notice that every child access changes one column bucket id. So 12 actually goes ahead of 11.
vertical by yavinci on 500px.com
public List<List<Integer>> verticalOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) {
        return res;
    }
    
    Map<Integer, ArrayList<Integer>> map = new HashMap<>();
    Queue<TreeNode> q = new LinkedList<>();
    Queue<Integer> cols = new LinkedList<>();

    q.add(root); 
    cols.add(0);

    int min = 0;
    int max = 0;
    
    while (!q.isEmpty()) {
        TreeNode node = q.poll();
        int col = cols.poll();
        
        if (!map.containsKey(col)) {
            map.put(col, new ArrayList<Integer>());
        }
        map.get(col).add(node.val);

        if (node.left != null) {
            q.add(node.left); 
            cols.add(col - 1);
            min = Math.min(min, col - 1);
        }
        
        if (node.right != null) {
            q.add(node.right);
            cols.add(col + 1);
            max = Math.max(max, col + 1);
        }
    }

    for (int i = min; i <= max; i++) {
        res.add(map.get(i));
    }

    return res;
}
Alternatively, we can calculate the rang first, then insert into buckets.
https://discuss.leetcode.com/topic/33411/3ms-java-solution-beats-100
There is no difference when using HashMap. Since by using HashMap it need keep track of min and max as well, I'd rather directly insert into list by computing min and max in advance.
public List<List<Integer>> verticalOrder(TreeNode root) {
    List<List<Integer>> cols = new ArrayList<>();
    if (root == null) {
        return cols;
    }
    
    int[] range = new int[] {0, 0};
    getRange(root, range, 0);
    
    for (int i = range[0]; i <= range[1]; i++) {
        cols.add(new ArrayList<Integer>());
    }
    
    Queue<TreeNode> queue = new LinkedList<>();
    Queue<Integer> colQueue = new LinkedList<>();
    
    queue.add(root);
    colQueue.add(-range[0]);
    
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        int col = colQueue.poll();
        
        cols.get(col).add(node.val);
        
        if (node.left != null) {
            queue.add(node.left);   
            colQueue.add(col - 1);
        } 
        if (node.right != null) {
            queue.add(node.right);
            colQueue.add(col + 1);
        }
    }
    
    return cols;
}

public void getRange(TreeNode root, int[] range, int col) {
    if (root == null) {
        return;
    }
    range[0] = Math.min(range[0], col);
    range[1] = Math.max(range[1], col);
    
    getRange(root.left, range, col - 1);
    getRange(root.right, range, col + 1);
}
https://leetcode.com/discuss/73113/using-hashmap-bfs-java-solution
Only need track min, not max level.
public List<List<Integer>> verticalOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<>(); if (root == null) { return res; } //map's key is column, we assume the root column is zero, the left node will minus 1 ,and the right node will plus 1 HashMap<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>(); Queue<TreeNode> queue = new LinkedList<>(); //use a HashMap to store the TreeNode and the according cloumn value HashMap<TreeNode, Integer> weight = new HashMap<TreeNode, Integer>(); queue.offer(root); weight.put(root, 0); int min = 0; while (!queue.isEmpty()) { TreeNode node = queue.poll(); int w = weight.get(node); if (!map.containsKey(w)) { map.put(w, new ArrayList<>()); } map.get(w).add(node.val); if (node.left != null) { queue.add(node.left); weight.put(node.left, w - 1); } if (node.right != null) { queue.add(node.right); weight.put(node.right, w + 1); } //update min ,min means the minimum column value, which is the left most node min = Math.min(min, w); } while (map.containsKey(min)) { res.add(map.get(min++)); } return res; }

public int index = 0;
public TreeMap<Integer, List<Integer>> tm;

public class Pair {
    TreeNode node;
    int index;
    public Pair(TreeNode n, int i) {
        node = n;
        index = i;
    }
}

public List<List<Integer>> verticalOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    tm = new TreeMap<Integer, List<Integer>>();
    if (root == null) return res;

    Queue<Pair> q = new LinkedList<Pair>();
    q.offer(new Pair(root, 0));

    while (!q.isEmpty()) {
        Pair cur = q.poll();
        if (!tm.containsKey(cur.index)) tm.put(cur.index, new ArrayList<Integer>());
        tm.get(cur.index).add(cur.node.val);

        if (cur.node.left != null) q.offer(new Pair(cur.node.left, cur.index-1));
        if (cur.node.right != null) q.offer(new Pair(cur.node.right, cur.index+1));
    }

    for (int key : tm.keySet()) res.add(tm.get(key));
    return res;
}
X. TreeMap
https://www.geeksforgeeks.org/print-binary-tree-vertical-order-set-2/
The above solution uses preorder traversal and Hashmap to store nodes according to horizontal distances. Since above approach uses preorder traversal, nodes in a vertical line may not be prined in same order as they appear in tree. For example, the above solution prints 12 before 9 in below tree. See this for a sample run.
    static void getVerticalOrder(Node root, int hd,
                                TreeMap<Integer,Vector<Integer>> m)
    {
        // Base case
        if(root == null)
            return;
          
        //get the vector list at 'hd'
        Vector<Integer> get =  m.get(hd);
          
        // Store current node in map 'm'
        if(get == null)
        {
            get = new Vector<>();
            get.add(root.key);
        }
        else
            get.add(root.key);
          
        m.put(hd, get);
          
        // Store nodes in left subtree
        getVerticalOrder(root.left, hd-1, m);
          
        // Store nodes in right subtree
        getVerticalOrder(root.right, hd+1, m);
    }
      
    // The main function to print vertical oder of a binary tree
    // with given root
    static void printVerticalOrder(Node root)
    {
        // Create a map and store vertical oder in map using
        // function getVerticalOrder()
        TreeMap<Integer,Vector<Integer>> m = new TreeMap<>();
        int hd =0;
        getVerticalOrder(root,hd,m);
          
        // Traverse the map and print nodes at every horigontal
        // distance (hd)
        for (Entry<Integer, Vector<Integer>> entry : m.entrySet())
        {
            System.out.println(entry.getValue());
        }
    }

http://www.itdadao.com/article/48930/
https://leetcode.com/discuss/79821/java-bfs-concise-code-using-2-maps
用了treemap来维护左右关系，其实也可以不用，记录一个min的index就好。
    public List<List<Integer>> verticalOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (root == null) {
            return result;
        }
        HashMap<TreeNode, Integer> map1 = new HashMap<TreeNode, Integer>();
        TreeMap<Integer, List<Integer>> map2 = new TreeMap<Integer, List<Integer>>();
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        map1.put(root, 0);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                int index = map1.get(node);
                List<Integer> list = map2.containsKey(index) ? map2.get(index) : new ArrayList<Integer>();
                list.add(node.val);
                map2.put(index, list);
                if (node.left != null) {
                    queue.offer(node.left);
                    map1.put(node.left, index - 1);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                    map1.put(node.right, index + 1);
                }
            }
        }
        Iterator<Integer> it = map2.keySet().iterator();
        while (it.hasNext()) {
            result.add(map2.get(it.next()));
        }
        return result;
    }
}
X. DFS
http://www.zrzahid.com/vertical-and-zigzag-traversal-of-binary-tree/
public static void verticalTrversal(BTNode root){
 int[] minmax = new int[]{Integer.MAX_VALUE, Integer.MIN_VALUE};
 Map<Integer, ArrayList<BTNode>> verticals = new HashMap<Integer, ArrayList<BTNode>>();
 traverse(root, verticals, 0, minmax);
 for(int i = minmax[0]; i<=minmax[1]; i++){
  if(verticals.containsKey(i)){
   for(BTNode vnode : verticals.get(i)){
    System.out.print(vnode.key+",");
   }
   System.out.println();
  }
 }
 
}

private static void traverse(BTNode node, Map<Integer, ArrayList<BTNode>> verticals, int score, int[] minmax){
 if(!verticals.containsKey(score)){
  verticals.put(score, new ArrayList<BTNode>());
 }
 
 verticals.get(score).add(node);
 minmax[0] = Math.min(minmax[0], score);
 minmax[1] = Math.max(minmax[1], score);
 
 if(node.left != null){
  traverse(node.left, verticals, score-1, minmax);
 }
 if(node.right != null){
  traverse(node.right, verticals, score+1, minmax);
 }
}
https://leetcode.com/discuss/77236/just-to-be-different-java-4-5-ms-95%25-dfs-solution
  1. First I traverse the tree and determine the min, max indices as well as the depth of the tree.
  2. I use these limits to construct a 2D array of size (max index - min index + 1). e.g. if min index = -2, and max index = 3, then the length of the array rows is 3 + 2 + 1(root).
  3. The length of the array columns is determined by the depth (I call it 'height') of the tree.
  4. I then create an empty ArrayList in each cell of our 2D array to handle the collisions. Note that I preallocate 2 slots of capacity for each ArrayList, since we can have at most 2 nodes competing for the same cell.
  5. Now that all the memory is preallocated I traverse the tree the second time and fill in the cells of the 2D array. Note that some of the cells will contain empty arrayLists in the end, so this is not the most space efficient method.


public List<List<Integer>> verticalOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) return res;
    int[] minmax = new int[3];

    getEnds(root, 0, 1, minmax);

    ArrayList<Integer>[][] tree = new ArrayList[minmax[1] - minmax[0] + 1][minmax[2]];
    for (int i = 0; i < tree.length; i++)
        for (int j = 0; j < tree[0].length; j++)
            tree[i][j] = new ArrayList<Integer>(2);

    order(root, 0, -minmax[0], 0, tree); 

    for (int i = 0; i < tree.length; i++) {
        res.add(new ArrayList<Integer>());
        for (int j = 0; j < tree[0].length; j++) {
            if (!tree[i][j].isEmpty()) {
                res.get(i).addAll(tree[i][j]);
            }
        }
    }
    return res;
}

private void order(TreeNode root, int level, int l, int height, ArrayList<Integer>[][] tree) {
    if (root == null) return;
    tree[l + level][height].add(root.val);
    order(root.left, level-1, l, height + 1, tree);
    order(root.right, level+1, l, height + 1, tree);
}

private void getEnds(TreeNode root, int level, int height, int[] minmax) {
    if (root == null) return;
    minmax[0] = Math.min(level, minmax[0]);
    minmax[1] = Math.max(level, minmax[1]);
    minmax[2] = Math.max(height, minmax[2]);
    getEnds(root.left, level-1, height + 1, minmax);
    getEnds(root.right, level+1, height + 1, minmax);
}
https://leetcode.com/discuss/73108/level-order-traversal-wrapping-nodes-with-a-shift-index
at
Labels: , , , , , ,

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts