662. Maximum Width of Binary Tree - Medium

前往題目

思路

1. 每個node都記錄其數字，左node都是parent的兩倍，右node都是parent的兩倍再加1
2. 利用BFS疊代所有node
3. 每層疊代完之後利用最邊的數字與最右邊的數字相減+1就是該層的寬度，檢查完每層之後就是答案

Code

Java版本

class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        int res = 0;
        Queue<Pair<TreeNode, Integer>> q = new LinkedList<>();
        // Add the root node and its corresponding number
        q.offer(new Pair(root, 1));

        while (!q.isEmpty()) {
            // Store the beginning
            int l = q.peek().getValue();
            // Current number
            int r = l; // or r = 0 whatever, it's just init.
            int size = q.size();

            for (int i = 0; i < size; ++i) {
                TreeNode currNode = q.peek().getKey();
                // Get current number
                r = q.poll().getValue();
                // Add left and right nodes
                if (currNode.left != null) {
                    q.offer(new Pair(currNode.left, 2 * r));
                }
                if (currNode.right != null) {
                    q.offer(new Pair(currNode.right, 2 * r + 1));
                }
            }
            res = Math.max(res, r - l + 1);
        }
        return res;
    }
}

2024/04/30

• 不難，不過還是看了思路才解出來