廖家龙的博客网站
LeetCode_662_二叉树最大宽度
廖家龙 用心听，不照做
  2019-06-30 13:44:00   2024-07-19 11:15:09    534 字  2 分钟

题目描述：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree）结构相同，但一些节点为空。

每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入长度）之间的长度。

示例：

输入: 

           1
         /   \
        3     2
       / \     \  
      5   3     9 

输出: 4
解释: 最大值出现在树的第 3 层，宽度为 4 (5,3,null,9)。

输入: 

          1
         /  
        3    
       / \       
      5   3     

输出: 2
解释: 最大值出现在树的第 3 层，宽度为 2 (5,3)。

输入: 

          1
         / \
        3   2 
       /        
      5      

输出: 2
解释: 最大值出现在树的第 2 层，宽度为 2 (3,2)。

输入: 

          1
         / \
        3   2
       /     \  
      5       9 
     /         \
    6           7
输出: 8
解释: 最大值出现在树的第 4 层，宽度为 8 (6,null,null,null,null,null,null,7)。

注意：答案在32位有符号整数的表示范围内。

解法1：广度优先遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {

        if (root == nullptr) return 0;
    
        int res = 0;  //返回的最大宽度值

        queue<TreeNode* > q;  //定义一个队列

        root->val = 0;  //假设根节点的编号为0

        q.push(root);

        while (!q.empty()) {

            //返回的最大宽度值
            res = max(res, q.back()->val - q.front()->val + 1);

            //❗️推演一下下面的两个例子
            //[1,3,2,5,3,null,9] 输出结果为4
            //[1,null,2,null,3] 输出结果为1
            int offset = q.front()->val;  //编号缩小的差值

            int n = q.size();

            for (int i = 0; i < n; ++i) {

                TreeNode* curr = q.front();

                q.pop();
            
                curr->val -= offset;  //缩小数值

                if (curr->left != nullptr) {

                    //转换为对应的编号
                    curr->left->val = curr->val * 2;
                    q.push(curr->left);
                }

                if (curr->right != nullptr) {

                    //转换为对应的编号
                    curr->right->val = curr->val * 2 + 1;
                    q.push(curr->right);
                }
            }
        }

        return res;
    }
};
  1. 1. 题目描述：
    1. 1.1. 解法1：广度优先遍历
  1. 1. 题目描述：
    1. 1.1. 解法1：广度优先遍历