Simple Concept Java Level Order Traversal 10ms


  • 0

    The idea is very simple. We can treat the tree as an array and every TreeNode has an attribute of its index in the array. The left child's index is parent.index2, the right child's index is parent.index2+1. Using level order traversal, two pointers will record the leftmost and rightmost index and the distance between both pointers would be the width of that level.

    class Solution {
        class Node {
            TreeNode node;
            int index;
            public Node(TreeNode node, int index) {
                this.node = node;
                this.index = index;
            }
        }
        public int widthOfBinaryTree(TreeNode root) {
            if (root == null) return 0;
            Queue<Node> queue = new LinkedList<>();
            queue.offer(new Node(root, 1));
            int res = 1;
            while (!queue.isEmpty()) {
                int size = queue.size();
                int l = -1, r = -1;
                for (int i = 0; i < size; i++) {
                    Node curr = queue.poll();
                    if (l == -1) l = curr.index;
                    else r = curr.index;
                    if (curr.node.left != null) queue.offer(new Node(curr.node.left, curr.index * 2));
                    if (curr.node.right != null) queue.offer(new Node(curr.node.right, curr.index * 2 + 1));
                }
                if (r != -1) res = Math.max(res, r - l + 1);
            }
            return res;
        }
    }
    

  • 0
    B

    Nice answer!


Log in to reply
 

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