LeetCode 662 Maximum Width of Binary Tree 二叉树的最大宽度

题目描述

Given a binary tree, write a function to get the maximum width of the given tree. The width of a tree is the maximum width among all levels. The binary tree has the same structure as a full binary tree, but some nodes are null.

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

本题是求解给定二叉树的最大宽度，这里的宽度指的是某一层最左端节点到最右端节点之间最多能放置的节点数，不是已有的节点数，也不是理论该层最多($2^n$2n)。而是某一层最左端非空和最右端非空节点之间的宽度，无论二者之间是不是完全填满，空位也算一个宽度。

讨论上述两个例子，
例1最下面一层叶子节点最左端是5，最右端是9，显然9的父节点只有右子节点而没有左子节点，但左子节点的位置仍然存在，还存在一个位置，因此其最大宽度是4.
例2最下层5,3两个节点，宽度为2，由于3节点是最右边的，其右边无法增加位置了。

解析

本题由于只考虑最左最右非空节点之间的差值，因此可以采用类似完全二叉树的编号方式，为每一个节点的位置编号，只要查看每一层出现的最小编号和最大编号就能知道该层的宽度了。对于完全二叉树，如根节点编号为0，两个子节点分别是1,2，对任意节点node编号为k，其左子节点node->left编号为$k*2+1$k∗2+1, 右子节点node->right编号为 $k*2+2$k∗2+2，我们采取逐行（BFS）的方式遍历二叉树，每个节点的子节点若存在，计算编号并将其保存下来，再设置一些判断，找到处于同一行的最左最右节点，设其编号分别为 left和right，则这一行宽度是$right-left+1$right−left+1
因此本题本质上是一个魔改的level order遍历
C++代码如下：

int solution::widthOfBinaryTree(TreeNode* root)
{
	if (!root)return 0;
	uint64_t ans = 0;
	queue<pair<TreeNode*, uint64_t>> q;
	q.push({ root,0 });
	TreeNode* last = root, * nextL = root;
	uint64_t left = 0, right = 0;
	bool newline = true;
	while (!q.empty()) {
		TreeNode* cur = q.front().first;
		uint64_t curNum = q.front().second;
		if (newline) left = curNum;
		right = curNum;
		q.pop();
		if (cur->left) {
			q.push({ cur->left,curNum * 2 + 1 });
		}
		if (cur->right) {
			q.push({ cur->right,curNum * 2 + 2 });
		}
		nextL = q.back().first;
		if (cur == last) {
			last = nextL;
			newline = true;
			//ans = max(ans, right - left + 1); //put max op here to Reduced computation
		}
		else newline = false;
		ans = max(ans, right - left + 1);
	}
	return (int)ans;
}

注意我这里的编号数据类型选择了uint64_t，没有直接用int(32bit)这也是为了通过leetcode本身的样例。由于我们不论每一层是否完全，下一层都按照乘2加1或加2的方式编号，如果遇到每一层只有一个节点的情况，编号增长就会很快。例如考虑每一层都只有左节点，其编号将是$0,1,3,7,15...2^{n-1}-1$0,1,3,7,15...2n−1−1这样，只要32个节点就表示了全部int的正整数范围，再多一个节点就溢出了。

这里用last和nextL分别记录当前行的最后一个和下一行的最后一个，这也是常见的level order遍历时区分每一行的做法，不同的是增加了一个newline用于判断当前节点是不是该行第一个以便定位left，right实际上可以在当前节点为last时再去取，宽度也是遇到last时再计算即可，如上述代码注释出，这样可以加快运算，减少不必要的计算量。
本质上就是在层序遍历基础上增加了完全二叉树的编号方式记录最左最右节点并计算宽度。