LeetCode_Queue_662. Maximum Width of Binary Tree 二叉樹最大寬度【隊列，疊代】【中等】

目錄

​​一，題目描述​​

​​英文描述​​

​​中文描述​​

​​示例與說明​​

​​二，解題思路​​

​​三，AC代碼​​

​​C++​​

​​Java​​

​​四，解題過程​​

​​第一博​​

一，題目描述

英文描述

Given the root of a binary tree, return the maximum width of the given tree.

The maximum width of a tree is the maximum width among all levels.

The width of one level is defined as the length between the end-nodes (the leftmost and rightmost non-null nodes), where the null nodes between the end-nodes are also counted into the length calculation.

It is guaranteed that the answer will in the range of 32-bit signed integer.

中文描述

給定一個二叉樹，編寫一個函數來擷取這個樹的最大寬度。樹的寬度是所有層中的最大寬度。這個二叉樹與滿二叉樹（full binary tree）結構相同，但一些節點為空。

每一層的寬度被定義為兩個端點（該層最左和最右的非空節點，兩端點間的null節點也計入長度）之間的長度。

示例與說明

來源：力扣（LeetCode）

連結：​​​https://leetcode-cn.com/problems/maximum-width-of-binary-tree​​ 著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

二，解題思路

參考​​@zrita【c++ 層序周遊-z】​​

采用BFS，循環一次處理一層的節點（進入循環時記錄隊列中元素數量count，隻彈出count個元素即可）。在處理每層的第一個節點時，記錄其位置start，便于後面的剪枝；

為每個節點标記其位置，每個節點的孩子編号分别為2*index、2*index+1，若不處理的話，很快會超過整型最大表示範圍；

有了起始位置和後面節點的位置，就可以友善的計算寬度curNode.index - start + 1，與ans比較并替換；

三，AC代碼

C++

class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        if (root == nullptr) return 0;
        queue<pair<TreeNode*, int>> q;
        q.push({root, 0});
        int ans = 0;
        while (!q.empty()) {
            int count = q.size();
            int start = q.front().second;// 記錄每一層的起點位置
            while (count--) {
                TreeNode* tem = q.front().first;
                int index = q.front().second;
                q.pop();
                // 這裡需要剪枝，否則會超出int類型表示的最大範圍
                if (tem->left) q.push({tem->left, 2 * index - 2 * start});
                if (tem->right) q.push({tem->right, 2 * index + 1 - 2 * start});
                ans = max(ans, index - start + 1);
            }
        }
        return ans;
    }
};      

Java

class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        if (root == null) return 0;
        Queue<AnnotatedNode> q = new LinkedList<>();
        q.offer(new AnnotatedNode(root, 0));
        int ans = 0;
        while (!q.isEmpty()) {
            int count = q.size();
            int start = q.peek().index;
            while (count-- != 0) {
                AnnotatedNode tem = q.poll();
                int index = tem.index;
                if (tem.node.left != null) q.offer(new AnnotatedNode(tem.node.left, 2 * index - 2 * start));
                if (tem.node.right != null) q.offer(new AnnotatedNode(tem.node.right, 2 * index + 1 - 2 * start));
                ans = Math.max(ans, index - start + 1);
            }
        }
        return ans;
    }
}
class AnnotatedNode {
    TreeNode node;
    int index;

    public AnnotatedNode(TreeNode node, int index) {
        this.node = node;
        this.index = index;
    }
}      

四，解題過程

第一博