数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中二叉树最大连续递增路径长度
假设我们有一个二叉树；我们必须计算由连续递增值节点组成的最长路径的长度。每个节点将被视为长度为 1 的路径。
因此，如果输入类似于
则输出将为 3，因为 (11, 12, 13) 是最大连续路径。
为了解决这个问题，我们将遵循以下步骤：
- 定义一个函数 solve()，它将接收根节点、前一个数据、前一个长度作为参数。
- 如果根节点不为零，则：
- 返回前一个长度
- 当前数据 := 根节点的值
- 如果当前数据等于前一个数据 + 1，则：
- 返回 solve(根节点的左子节点, 当前数据, 前一个长度+1) 和 solve(根节点的右子节点, 当前数据, 前一个长度+1) 中的最大值
- 新路径长度 := solve(根节点的左子节点, 当前数据, 1) 和 solve(根节点的右子节点, 当前数据, 1) 中的最大值
- 返回前一个长度和新路径长度中的最大值
- 从主方法执行以下操作：
- 如果根节点等于 NULL，则：
- 返回 0
- 返回 solve(根节点, 根节点的值-1, 0)
示例 (C++)
让我们看看以下实现以更好地理解：
#include <bits/stdc++.h>
using namespace std;
class TreeNode {
public:
int val;
TreeNode *left, *right;
TreeNode(int data) {
val = data;
left = NULL;
right = NULL;
}
};
int solve(TreeNode *root, int prev_data, int prev_length){
if (!root)
return prev_length;
int cur_data = root->val;
if (cur_data == prev_data+1){
return max(solve(root->left, cur_data, prev_length+1), solve(root->right, cur_data, prev_length+1));
}
int newPathLen = max(solve(root->left, cur_data, 1), solve(root->right, cur_data, 1));
return max(prev_length, newPathLen);
}
int maxLen(TreeNode *root){
if (root == NULL)
return 0;
return solve(root, root->val-1, 0);
}
int main(){
TreeNode *root = new TreeNode(10);
root->left = new TreeNode(11);
root->right = new TreeNode(9);
root->left->left = new TreeNode(13);
root->left->right = new TreeNode(12);
root->right->left = new TreeNode(13);
root->right->right = new TreeNode(8);
cout << maxLen(root);
return 0;
}输入
TreeNode *root = new TreeNode(10); root->left = new TreeNode(11); root->right = new TreeNode(9); root->left->left = new TreeNode(13); root->left->right = new TreeNode(12); root->right->left = new TreeNode(13); root->right->right = new TreeNode(8);
输出
3
更新于: 2020-08-27
186 次浏览
广告