二叉树最大宽度(C++实现)

文章目录

题目一：计算宽度包含null结点题目二：计算宽度不包含null结点

题目一：计算宽度包含null结点

描述： 给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree）结构相同，但一些节点为空。 每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入长度）之间的长度。 思路：

每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入长度）之间的长度 使用完全二叉树的索引组织节点： 根节点索引为0 左子节点索引 = 父节点索引 * 2 + 1 右子节点索引 = 父节点索引 * 2 + 2 层的宽度 = 该层最右边的节点索引 - 该层最左边的节点索引 + 1

代码：

/** * 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: // 将结点与索引封装起来 struct Data { TreeNode* cur; unsigned int index; Data(TreeNode* node, int i) : cur(node), index(i) {} }; int widthOfBinaryTree(TreeNode* root) { if (root == nullptr) { return 0; } queue<Data> q; q.emplace(root, 0); unsigned int max_width = 0; while (!q.empty()) { unsigned int q_size = q.size(); unsigned int left_index = q.front().index; unsigned int right_index; for (int i = 0; i < q_size; ++i) { Data tmp = q.front(); q.pop(); if (tmp.cur->left) { q.emplace(tmp.cur->left, tmp.index * 2 + 1); } if (tmp.cur->right) { q.emplace(tmp.cur->right, tmp.index * 2 + 2); } if (i == q_size - 1) { right_index = tmp.index; } } max_width = max(max_width, right_index - left_index + 1); } return max_width; } };

题目二：计算宽度不包含null结点

描述： 不包含null结点，就求出每层的结点个数，求出最大值。

思路： 要比题目一容易，因为每次只要计算当前队列元素的个数，就是每层的个数。

也可以记录当前下一层最后结点的地址，每次遇到该层尾巴结点，就可以得出该层结点的个数。（代码如下）

代码：

int treeMaxWidthNoMap(TreeNode* head) { int maxWidth = 0; if (head == nullptr) { return maxWidth; } // 用队列实现 queue<TreeNode*> q; q.push(head); TreeNode* curEnd = head; //记录当前层的尾巴 TreeNode* nextEnd = nullptr; //记录下一层的尾巴 int curWidth = 0; while (!q.empty()) { TreeNode* node = q.front(); q.pop(); // 更新下一层尾巴 if (node->left != nullptr) { q.push(node->left); nextEnd = node->left; } if (node->right != nullptr) { q.push(node->right); nextEnd = node->right; } curWidth++; // 如果当前结点是该层的尾巴 if (node == curEnd) { maxWidth = max(maxWidth, curWidth); curWidth = 0; curEnd = nextEnd; } } return maxWidth; }