LeetCode 662 - Maximum Width of Binary Tree


https://leetcode.com/problems/maximum-width-of-binary-tree
Given a binary tree, write a function to get the maximum width of the given tree. The width of a tree is the maximum width among all levels. The binary tree has the same structure as a full binary tree, but some nodes are null.
The width of one level is defined as the length between the end-nodes (the leftmost and right most non-null nodes in the level, where the null nodes between the end-nodes are also counted into the length calculation.
Example 1:
Input: 

           1
         /   \
        3     2
       / \     \  
      5   3     9 

Output: 4
Explanation: The maximum width existing in the third level with the length 4 (5,3,null,9).
X. DFS
http://www.voidcn.com/article/p-fvunixcy-bnv.html
实现的思路是用两个hashmap保存当前层的index, minMap保存当前层最左边的节点的index, maxMap则保存最后边的节点的index。 minMap每一层只需要存储一次,(第一次), maxMap 则需要不断的更新,因为不确定当前的点是否是最右侧的。 最后统计一下每一层的最大值。如果不存在最大或者最小值,那么就跳过这一层。
    public int widthOfBinaryTree(TreeNode root) {
        if(root == null) return 0;

        HashMap<Integer, Integer> minMap = new HashMap<>();
        HashMap<Integer, Integer> maxMap = new HashMap<>();
        dfs(minMap, maxMap, root, 0, 0);
        int max = Integer.MIN_VALUE;
        for(int i=0;i<maxMap.size();i++) {
            if(!maxMap.containsKey(i) || !minMap.containsKey(i)) continue;
            max = Math.max(max, maxMap.get(i) - minMap.get(i));

        }
        return max;
    }

    private void dfs(HashMap<Integer, Integer> minMap,
                     HashMap<Integer, Integer> maxMap,
                     TreeNode node,
                     int layer, int index) {
        if(node == null) return;
        if(!minMap.containsKey(layer)) minMap.put(layer, index);
        if(!maxMap.containsKey(layer)
                || maxMap.get(layer)<index) {
            maxMap.put(layer, index);
        }

        if(node.left != null) {
            dfs(minMap, maxMap, node.left, layer+1, index*2);

        }
        if(node.right != null) {
            dfs(minMap, maxMap, node.right, layer+1, index*2+1);

        }
    }
We know that a binary tree can be represented by an array (assume the root begins from the position with index 1 in the array). If the index of a node is i, the indices of its two children are 2*i and 2*i + 1. The idea is to use two arrays (start[] and end[]) to record the the indices of the leftmost node and rightmost node in each level, respectively. For each level of the tree, the width isend[level] - start[level] + 1. Then, we just need to find the maximum width.
Java version:
    public int widthOfBinaryTree(TreeNode root) {
        return dfs(root, 0, 1, new ArrayList<Integer>(), new ArrayList<Integer>());
    }
    
    public int dfs(TreeNode root, int level, int order, List<Integer> start, List<Integer> end){
        if(root == null)return 0;
        if(start.size() == level){
            start.add(order); end.add(order);
        }
        else end.set(level, order);
        int cur = end.get(level) - start.get(level) + 1;
        int left = dfs(root.left, level + 1, 2*order, start, end);
        int right = dfs(root.right, level + 1, 2*order + 1, start, end);
        return Math.max(cur, Math.max(left, right));
    }
X. Only need store id of left most node in each layer
https://segmentfault.com/a/1190000017149507
https://leetcode.com/problems/maximum-width-of-binary-tree/discuss/106645/cjava-bfsdfs3liner-clean-code-with-explanation
The idea is to use heap indexing:
        1
   2         3
 4   5     6   7
8 9 x 11  x 13 x 15
Regardless whether these nodes exist:
  • Always make the id of left child as parent_id * 2;
  • Always make the id of right child as parent_id * 2 + 1;
So we can just:
  1. Record the id of left most node at each level of the tree(you can tell be check the size of the container to hold the first nodes);
  2. At each node, compare the distance from it the left most node with the current max width;
    public int widthOfBinaryTree(TreeNode root) {
        List<Integer> lefts = new ArrayList<Integer>(); // left most nodes at each level;
        int[] res = new int[1]; // max width
        dfs(root, 1, 0, lefts, res);
        return res[0];
    }
    private void dfs(TreeNode node, int id, int depth, List<Integer> lefts, int[] res) {
        if (node == null) return;
        if (depth >= lefts.size()) lefts.add(id);   // add left most node
        res[0] = Integer.max(res[0], id + 1 - lefts.get(depth));
        dfs(node.left,  id * 2,     depth + 1, lefts, res);
        dfs(node.right, id * 2 + 1, depth + 1, lefts, res);
    }
https://discuss.leetcode.com/topic/100128/java-solution-node-position-of-binary-tree
    Map<Integer, int[]> map = new HashMap<>();
    
    public int widthOfBinaryTree(TreeNode root) {
        if (root == null) return 0;
        
        findMax(root, 0, 0);
        
        int res = 1;
        for (int[] rec : map.values()) {
            res = Math.max(res, rec[1] - rec[0] + 1);
        }
        
        return res;
    }
    
    private void findMax(TreeNode root, int level, int pos) {
        if (root == null) return;
        
        int[] rec = map.get(level);
        if (rec == null) {
            rec = new int[2];
            rec[0] = Integer.MAX_VALUE;
            rec[1] = Integer.MIN_VALUE;
        }

        rec[0] = Math.min(rec[0], pos);
        rec[1] = Math.max(rec[1], pos);
        map.put(level, rec);
        
        findMax(root.left, level + 1, 2 * pos);
        findMax(root.right, level + 1, 2 * pos + 1);
    }

X. BFS
BFS: using dequeue
https://leetcode.com/problems/maximum-width-of-binary-tree/discuss/106663/Java-O(n)-BFS-one-queue-clean-solution
change the val of node to be the index to save space. The value is useless. All we need is just the index.
this is a bit intrusive by changing the treenode val, right?
class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        if (root == null) {
            return 0;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        root.val = 0;
        int max = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            max = Math.max(max, queue.peekLast().val - queue.peekFirst().val + 1);
            for (int i = 0; i < size; i++) {
                root = queue.poll();
                if (root.left != null) {
                    root.left.val = root.val * 2;
                    queue.offer(root.left);
                }
                if (root.right != null) {
                    root.right.val = root.val * 2 + 1;
                    queue.offer(root.right);
                }
            }
        }
        return max;
    }
https://leetcode.com/problems/maximum-width-of-binary-tree/discuss/106659/JAVA-Easy-to-understand-solution.-(BFS)

https://leetcode.com/articles/maximum-width-of-binary-tree/
  public int widthOfBinaryTree(TreeNode root) {
    Queue<AnnotatedNode> queue = new LinkedList();
    queue.add(new AnnotatedNode(root, 0, 0));
    int curDepth = 0, left = 0, ans = 0;
    while (!queue.isEmpty()) {
      AnnotatedNode a = queue.poll();
      if (a.node != null) {
        queue.add(new AnnotatedNode(a.node.left, a.depth + 1, a.pos * 2));
        queue.add(new AnnotatedNode(a.node.right, a.depth + 1, a.pos * 2 + 1));
        if (curDepth != a.depth) {
          curDepth = a.depth;
          left = a.pos;
        }
        ans = Math.max(ans, a.pos - left + 1);
      }
    }
    return ans;
  }
}

class AnnotatedNode {
  TreeNode node;
  int depth, pos;

  AnnotatedNode(TreeNode n, int d, int p) {
    node = n;
    depth = d;
    pos = p;
  }

}
    public int widthOfBinaryTree(TreeNode root) {
        if (root == null) return 0;
        int max = 0;
        Queue<Map.Entry<TreeNode, Integer>> q = new LinkedList<Map.Entry<TreeNode, Integer>>();
        q.offer(new AbstractMap.SimpleEntry(root, 1));

        while (!q.isEmpty()) {
            int l = q.peek().getValue(), r = l; // right started same as left
            for (int i = 0, n = q.size(); i < n; i++) {
                TreeNode node = q.peek().getKey();
                r = q.poll().getValue();
                if (node.left != null) q.offer(new AbstractMap.SimpleEntry(node.left, r * 2));
                if (node.right != null) q.offer(new AbstractMap.SimpleEntry(node.right, r * 2 + 1));
            }
            max = Math.max(max, r + 1 - l);
        }

        return maxwidth;
    }
https://blog.csdn.net/TheSnowBoy_2/article/details/77430277
  public int widthOfBinaryTree(TreeNode root) {
    if (root == null) {
      return 0;
    }
    Queue<TreeNode> queue = new LinkedList<>(); // 用于树的广度优先遍历。
    Queue<Integer> queuePos = new LinkedList<>(); // 用于保存上面队列中树节点对应的位置标号。
    queue.add(root);
    queuePos.add(1);// 在顶层跟结点位置为1.

    int countCurrent = 1;// 记录正在遍历的当前层次的剩余数量。
    int countTmp = 0; // 记录下一层次结点的数量。
    int max = countCurrent; // 记录最大的差距。(目标)(与start 和 end相关)
    int start = 1;// 记录某层次结点的最左边的结点。
    int end = 1;// 记录某层次结点的最右边的结点。

    while (!queue.isEmpty()) {

      TreeNode current = queue.poll();
      end = queuePos.poll();

      if (current.left != null) {
        queue.add(current.left);
        queuePos.add(2 * end);// 分配左孩子结点的序号。
        countTmp++;// 记录下层结点的数量
      }
      if (current.right != null) {
        queue.add(current.right);
        queuePos.add(2 * end + 1); // 分配右孩子结点的序号
        countTmp++;
      }

      // 当前层次已遍历完毕,计算max,并且为下一层次的遍历准备。
      if (--countCurrent == 0) {
        // 目标比对。
        if (max < end - start + 1) {
          max = end - start + 1;
        }
        countCurrent = countTmp;// 设置下一层次剩余的数量
        countTmp = 0;
        // 设置下一层结点的start.
        start = queuePos.isEmpty() ? 1 : queuePos.peek();

      }
    }
    return max;

  }


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