1. 从树到二叉树的魔法：左孩子右兄弟表示法

第一次听说"左孩子右兄弟"表示法时，我正对着考研真题里那棵枝繁叶茂的树发呆。传统树结构的多叉特性让算法实现变得复杂，直到我发现这个将任意树转化为二叉树的"算法密码"。

这种表示法的精妙之处在于：用二叉链表的结构存储普通树。具体规则是：

• 左指针指向该节点的第一个孩子（长子）
• 右指针指向该节点的右侧兄弟

举个例子，假设我们有这样一棵家谱树：

A / | \ B C D / \ \ E F G

转化为左孩子右兄弟表示法后：

A / B / \ E C \ / \ F D G

这种转换不是随意为之。在2019年某校考研真题中，就出现过这样的应用题："将森林F={T1,T2,T3}转换为二叉树，并说明转换后二叉树的高度与森林中树的关系"。这正是考察左孩子右兄弟表示法的典型场景。

2. 核心操作实战：四大基础算法实现

2.1 树的高度计算

在传统树结构中计算高度需要复杂的递归，而转换后的二叉树高度计算变得异常简单：

int TreeHeight(TreeNode* t) { if (!t) return 0; int leftHeight = TreeHeight(t->left); // 长子链的高度 int rightHeight = TreeHeight(t->right);// 兄弟链的高度 return (leftHeight + 1) > rightHeight ? (leftHeight + 1) : rightHeight; }

这个算法的精妙之处在于：左子树代表向下探索深度，右子树代表横向比较宽度。实测下来，对于n个节点的树，时间复杂度稳定在O(n)。

2.2 叶子节点计数

判断标准很特别：没有左孩子的节点就是原树的叶子节点。这与普通二叉树的定义不同：

int CountLeaves(TreeNode* t) { if (!t) return 0; if (!t->left) return 1 + CountLeaves(t->right); return CountLeaves(t->left) + CountLeaves(t->right); }

在2021年考研真题中，就出现过类似的变种题："计算森林的终端节点数"。掌握这个算法就能快速解决。

2.3 树的遍历玄机

树的遍历在转换后变得有趣：

• 先根遍历= 二叉树的前序遍历
• 后根遍历= 二叉树的中序遍历

// 先根遍历 void PreOrder(TreeNode* t) { if (!t) return; printf("%c ", t->val); TreeNode* p = t->left; while (p) { PreOrder(p); p = p->right; } } // 后根遍历 void PostOrder(TreeNode* t) { if (!t) return; TreeNode* p = t->left; while (p) { PostOrder(p); p = p->right; } printf("%c ", t->val); }

特别提醒：后根遍历时，兄弟节点的处理顺序会影响结果。这是很多同学容易出错的地方。

3. 进阶应用：解决复杂树形问题

3.1 层次遍历的改造

普通二叉树的层次遍历需要调整才能适用于这种结构：

void LevelTraversal(TreeNode* t) { if (!t) return; queue<TreeNode*> q; q.push(t); while (!q.empty()) { int levelSize = q.size(); while (levelSize--) { TreeNode* curr = q.front(); q.pop(); printf("%c ", curr->val); // 关键点：将当前节点的所有孩子入队 TreeNode* child = curr->left; while (child) { q.push(child); child = child->right; } } printf("\n"); // 打印完一层换行 } }

这种遍历方式在求树的宽度时特别有用，只需要记录每层节点的最大值即可。

3.2 寻找双亲节点

在没有parent指针的情况下，如何找到某个节点的双亲？这是一个经典的考研算法题：

TreeNode* FindParent(TreeNode* root, TreeNode* target) { if (!root || root == target) return NULL; TreeNode* child = root->left; while (child) { if (child == target) return root; TreeNode* res = FindParent(child, target); if (res) return res; child = child->right; } return NULL; }

这个算法采用了深度优先搜索策略，时间复杂度为O(n)。在2018年某校的机试题中，曾出现过需要在此基础上统计某节点所有祖先的变种题目。

4. 考研真题实战解析

让我们看一道综合应用题："给定一棵树的左孩子右兄弟表示法存储的二叉树，编写算法判断节点p和q是否为堂兄弟节点（同一层且不同父节点）"

解题思路分三步：

1. 判断两节点是否在同一层
2. 查找它们的父节点
3. 验证父节点是否不同

bool IsCousin(TreeNode* root, TreeNode* p, TreeNode* q) { if (!root || p == q) return false; // 使用队列进行层次遍历 queue<pair<TreeNode*, TreeNode*>> q; // 存储<节点,父节点> q.push({root, NULL}); TreeNode *pParent = NULL, *qParent = NULL; int found = 0; while (!q.empty() && found < 2) { int size = q.size(); for (int i = 0; i < size; ++i) { auto [node, parent] = q.front(); q.pop(); if (node == p) { pParent = parent; found++; } if (node == q) { qParent = parent; found++; } TreeNode* child = node->left; while (child) { q.push({child, node}); child = child->right; } } if (found == 1) return false; // 不在同一层 if (found == 2) return pParent != qParent; } return false; }

这类题目在近5年的考研中出现了3次，掌握左孩子右兄弟表示法的特性是解题关键。