以二叉链表作为二叉树的存储结构。设计C++算法求二叉树中第一条最长的路径长度,并输出此路径上各结点的值。
时间: 2023-11-28 11:49:45 浏览: 108
实际上,求二叉树中第一条最长的路径长度,可以通过求根节点的左右子树的深度之和来实现。具体实现方法如下:
```c++
#include<iostream>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
int maxDepth(TreeNode* root) {
if (root == nullptr) return 0;
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
maxLen = max(maxLen, leftDepth + rightDepth);
return max(leftDepth, rightDepth) + 1;
}
void findLongestPath(TreeNode* root) {
if (root == nullptr) return;
if (maxDepth(root->left) + maxDepth(root->right) == maxLen) {
cout << root->val << " ";
findLongestPath(root->left);
findLongestPath(root->right);
}
else if (maxDepth(root->left) == maxLen) {
findLongestPath(root->left);
}
else {
findLongestPath(root->right);
}
}
int getLongestPath(TreeNode* root) {
maxLen = 0;
maxDepth(root);
findLongestPath(root);
return maxLen;
}
private:
int maxLen;
};
int main() {
TreeNode* node1 = new TreeNode(1);
TreeNode* node2 = new TreeNode(2);
TreeNode* node3 = new TreeNode(3);
TreeNode* node4 = new TreeNode(4);
TreeNode* node5 = new TreeNode(5);
TreeNode* node6 = new TreeNode(6);
TreeNode* node7 = new TreeNode(7);
TreeNode* node8 = new TreeNode(8);
node1->left = node2;
node1->right = node3;
node2->left = node4;
node2->right = node5;
node3->left = node6;
node6->right = node7;
node5->left = node8;
Solution solution;
int maxLen = solution.getLongestPath(node1);
cout << "The longest path length is: " << maxLen << endl;
return 0;
}
```
在上面的代码中,我们定义了一个`Solution`类,其中包含三个函数:
- `maxDepth`函数:求以当前节点为根的子树的深度,并且更新最长路径长度。
- `findLongestPath`函数:根据最长路径长度,找到第一条最长的路径,并输出路径上的节点值。
- `getLongestPath`函数:计算整个二叉树的最长路径长度,并且调用`findLongestPath`函数输出路径上的节点值。
最后我们在`main`函数中构造了一个二叉树,并且调用`getLongestPath`函数来计算最长路径长度,并输出路径上的节点值。
阅读全文