高效的LeetCode二叉树本地IDE调试方案

在 LeetCode 刷题过程中，有时候遇到一些难以难以直接观察出来的错误，此时通常想要利用单步调试来解决，但奈何只有 LeetCode Plus 会员才可以使用其网页的调试功能。好在绝大部分本地 IDE 都具备十分强大的调试功能，我们只需要将自己的解题代码复制到本地，并编写简单的测试程序即可。但是对于二叉树相关的题，测试数据的编写显得不那么容易，本文编写了一个匹配 LeetCode 题目中的二叉树定义的类，该类包含一些基本的静态函数，能够很方便地实现二叉树的构造和二叉树的遍历。

LeetCode 二叉树的序列表示方式

LeetCode 中针对二叉树的输入数据以一个层序遍历序列的形式给出。与通常我们所说的层序序列不同的是，该层序序列包含从根节点到最后一个非空结点之间的所有空结点，该空结点以 null 的标识符给出，以此保证根据此序列所构造二叉树的唯一性（单纯依靠常规的不含空结点的层序序列无法构造一棵唯一的二叉树）。以下是一个简单的例子：

输入： root = [3, 9, 20, null, null, 15, 7]

带构造与遍历的二叉树类

为了方便能在本地 IDE 中直接根据输入数据的格式构造二叉树，本文编写了两个简单的静态方法，来方便数据的输入与输出。

#define null INT32_MAX
struct TreeNode {
	int val;
	TreeNode* left, * right;
	TreeNode(int val = 0, TreeNode* left = nullptr, TreeNode* right = nullptr)
		: val(val), left(left), right(right) {}
	// 带空结点的层序遍历
	static void orderTraversalWithNull(TreeNode* root) {
		if (root == nullptr) return;
		queue<TreeNode*> q;
		q.emplace(root);
		vector<string> buf; // 输出缓冲
		while (!q.empty()) {
			TreeNode* fNode = q.front();
			q.pop();
			if (fNode == nullptr) {
				buf.emplace_back("null");
				continue;
			}
			buf.emplace_back(to_string(fNode->val));
			q.emplace(fNode->left);
			q.emplace(fNode->right);
		}
		while (buf.back() == "null") {
			buf.pop_back(); // 去除末尾多余的空结点
		}
		for (const auto& val : buf) {
			cout << val << " ";
		}
	}
	// 根据层序序列创建二叉树
	static TreeNode* createTreeByOrder(vector<int>& order) {
		if (order.empty() || order.front() == null) return nullptr;
		queue<TreeNode*> q;
		int idx = 0; // 指向当前结点的子结点
		TreeNode* root = new TreeNode(order[idx++]);
		q.emplace(root);
		while (!q.empty()) {
			TreeNode* fNode = q.front();
			q.pop();
			if (fNode == nullptr) continue;
			if (idx < order.size()) {
				TreeNode* lChild = nullptr;
				if (order[idx] != null) {
					lChild = new TreeNode(order[idx]);
				}
				fNode->left = lChild;
				q.emplace(lChild);
				++idx;
			}
			if (idx < order.size()) {
				TreeNode* rChild = nullptr;
				if (order[idx] != null) {
					rChild = new TreeNode(order[idx]);
				}
				fNode->right = rChild;
				q.emplace(rChild);
				++idx;
			}
		}
		return root;
	}
};

使用的方法也很简单，由于两个方法都是 TreeNode 类中的静态方法，可使用 :: 符对其进行调用。

int main() {
	vector<int> order = { 3,9,20,null,null,15,7 };
	TreeNode* root = TreeNode::createTreeByOrder(order);
	func(root);
	TreeNode::orderTraversalWithNull(root);
}