P8603 [蓝桥杯 2013 国 C] 横向打印二叉树 题解

· · 题解

P8603 [蓝桥杯 2013 国 C] 横向打印二叉树 题解

分析

吐槽：题目其实很不清晰，横向打印的定义都没讲，即使要求很显然，也不应让选手必须结合样例理解。

根据题意模拟即可。

我们把问题拆解开来：

  1. 建树。
  2. 确定节点纵坐标。
  3. 确定节点横坐标。
  4. 连接节点。

建树

建树很简单，相信学过二叉搜索树（Binary Search Tree, BST）的都会，但这里我还是再讲一下。

根据 BST 的性质（题目里也讲了），左儿子 < 根节点 < 右儿子，因此插入新节点时，就不断按照这一规则，直到找到一个空位再插入。

:::info[C++]

// BST 节点
// 这里采用指针式写法
struct TreeNode {
  int val;               // 权值
  TreeNode* l{nullptr};  // 左儿子
  TreeNode* r{nullptr};  // 右儿子
} tree[105];
TreeNode* root;  // 根节点

// 递归插入节点
TreeNode* insert(TreeNode* root, int x) {
  if (root == nullptr)  // 找到空位
    return new TreeNode{x};
  if (x < root->val)  // 待插入节点小于根节点则往左子树找
    root->l = insert(root->l, x);
  else  // 否则往右子树找
    root->r = insert(root->r, x);
  return root;
}

:::

（其实我一开始也不知道怎么写，还是翻了以前写的 BST 模板才写出来的，就当是复习基础算法了）

确定节点纵坐标

观察样例：

...|-12
10-|
...|-8-|
.......|...|-7
.......|-5-|
...........|-4

去除多余信息：

12
10
8
7
5
4

不难发现，节点的纵坐标实际上就是中序遍历序号，也就是按权值排序，自下至上递增，而且输出结果的行数正好是节点数量，所以我们绘图的时候就需要使用中序遍历。

:::info[简易的中序遍历]

void dfs(TreeNode* root) {
  if (root == nullptr)
    return;
  dfs(root->l);
  cout << root->val << ' ';
  dfs(root->r);
}

:::

确定节点横坐标

依旧观察样例，可以发现，节点的横坐标其实就类似深度，是由父节点决定的。

因此，我们计算当前节点的宽度，即前缀 |-、节点权值、后缀 -| 的长度和，在进入下一层 dfs 时，我们将深度加上当前节点的宽度。

连线

还是观察样例，我们会发现，权值为 5 和 8 的节点，除了前后缀以外，中间还有一条连线 |。

不难想到，我们让 dfs 函数返回一个整数——当前节点所处的列，这样我们只要在相应深度连线就行了。

完整代码

Talk is cheap, show me the code.

:::info[C++]

#include <iostream>

using namespace std;

// BST 节点
// 这里采用指针式写法
struct TreeNode {
  int val;               // 权值
  TreeNode* l{nullptr};  // 左儿子
  TreeNode* r{nullptr};  // 右儿子
} tree[105];
TreeNode* root;  // 根节点

// 递归插入节点
TreeNode* insert(TreeNode* root, int x) {
  if (root == nullptr)  // 找到空位
    return new TreeNode{x};
  if (x < root->val)  // 待插入节点小于根节点则往左子树找
    root->l = insert(root->l, x);
  else  // 否则往右子树找
    root->r = insert(root->r, x);
  return root;
}

int row = 0;
string ans[105];

// 将 pattern 插入在 main 的下标 pos 位置，不足部分用'.'补足
void insert_string(string& main, string pattern, int pos) {
  if (main.size() < pos + pattern.size())
    main += string(pos + pattern.size() - main.size(), '.');
  for (int i = 0; i < pattern.size(); i++)
    main[pos + i] = pattern[i];
}

int dfs(TreeNode* root, int depth = 0) {
  if (root == nullptr)
    return row;
  // 生成当前节点标签
  string label;
  if (depth)  // 根节点以外的节点都有父节点
    label += "|-";
  label += to_string(root->val);  // 权值
  if (root->l || root->r)  // 检查是否有子节点
    label += "-|";
  depth += label.size() - 1;  // 缩进
  // 左子树
  int left_row = dfs(root->l, depth);
  for (int i = left_row + 1; i < row; i++)
    insert_string(ans[i], "|", depth);
  // 绘制节点
  insert_string(ans[row], label, depth - label.size() + 1);  // 需要暂时取消缩进
  int current_row = row++;
  // 右子树
  int right_row = dfs(root->r, depth);
  for (int i = current_row + 1; i < right_row; i++)
    insert_string(ans[i], "|", depth);

  return current_row;
}

int main() {
  int x;
  while (cin >> x)
    root = insert(root, x);
  dfs(root);
  // 倒序输出
  for (int i = row - 1; i >= 0; i--)
    cout << ans[i] << endl;
  return 0;
}

:::