第6关：基于二叉链表的二叉树最长路径的求解

### 基于二叉链表实现的二叉树中最长路径求解 在基于二叉链表实现的二叉树中，最长路径是指从根节点到叶节点经过的最大边数。为了找到这条路径，可以采用深度优先搜索（DFS）策略来遍历整棵树并记录最大路径长度。 #### 定义二叉树节点结构 首先定义二叉树节点的数据结构： ```c++ struct TreeNode { char val; TreeNode *left, *right; TreeNode(char v) : val(v), left(nullptr), right(nullptr) {} }; ``` #### 构建二叉树函数 根据给定的先序序列构建二叉树： ```cpp TreeNode* buildTree(const string& preorder, int &index) { if (preorder[index] == '0') { // 遇到空结点 index++; return nullptr; } TreeNode* node = new TreeNode(preorder[index++]); node->left = buildTree(preorder, index); node->right = buildTree(preorder, index); return node; } ``` #### 计算最长路径辅助函数 计算任意两叶子之间的距离，并更新全局变量 `maxDiameter` 来保存当前发现的最大直径： ```cpp int maxDepth(TreeNode* root, int &maxDiameter) { if (!root) return 0; int leftHeight = maxDepth(root->left, maxDiameter); int rightHeight = maxDepth(root->right, maxDiameter); // 更新最大直径 maxDiameter = std::max(maxDiameter, leftHeight + rightHeight); return std::max(leftHeight, rightHeight) + 1; } ``` #### 主调用逻辑 最后，在主程序里读取多组测试案例并对每一棵由先序序列构成的二叉树执行上述操作: ```cpp #include <iostream> using namespace std; // ... 上述定义 ... void solve() { while(true){ string input; cin >> input; if(input=="0") break; int idx=0; TreeNode* treeRoot = buildTree(input,idx); int diameter = 0; maxDepth(treeRoot,diameter); cout << "The longest path length is:"<<diameter<<endl; } } int main(){ solve(); return 0; } ``` 此代码实现了通过先序序列创建一棵二叉树，并利用递归方式查找其内部存在的最远两个端点间的路径长度[^1][^2]。