数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究具有最大弯曲次数的C++路径长度
为了解决一个给定二叉树的问题。现在我们需要找到具有最大弯曲次数的路径。即，当路径的方向从左到右或从右到左改变时，就认为存在一个弯曲，例如
输入：
输出：
6
在这个方法中，我们将遍历树并跟踪之前的移动。如果方向改变，我们只需更新我们的弯曲计数，然后找到最大值。
寻找解决方案的方法
在这个方法中，我们将遍历所有路径，并找到最大弯曲次数来更新我们的答案。
示例
#include <bits/stdc++.h>
using namespace std;
struct Node { // structure of our node
int key;
struct Node* left;
struct Node* right;
};
struct Node* newNode(int key){ // initializing our node
struct Node* node = new Node();
node->left = NULL;
node->right = NULL;
node->key = key;
return node;
}
void maximumBends(struct Node* node,char direction, int bends,
int* maxBends, int soFar,int* len){
if (node == NULL) // if null is reached
return;
if (node->left == NULL && node->right == NULL) { // if we reach the leaf node then
//we check if we have to update our answer or not
if (bends > *maxBends) {
*maxBends = bends;
*len = soFar;
}
}
else {
if (direction == 'l') { // current direction is left
maximumBends(node->left, direction,bends, maxBends,soFar + 1, len);
maximumBends(node->right, 'r',bends + 1, maxBends,soFar + 1, len); // if we change direction so bend also increases
}
else {
maximumBends(node->right, direction,bends, maxBends,soFar + 1, len);
maximumBends(node->left, 'l',bends + 1, maxBends,soFar + 1, len); // same as when direction was left
}
}
}
int main(){
struct Node* root = newNode(10);
root->left = newNode(8);
root->right = newNode(2);
root->left->left = newNode(3);
root->left->right = newNode(5);
root->right->left = newNode(2);
root->right->left->right = newNode(1);
root->right->left->right->left = newNode(9);
int len = 0, bends = 0, maxBends = -1;
if(!root) // if tree is empty
cout << "0\n";
else{
if (root->left) // if left subtree exists
maximumBends(root->left, 'l',bends, &maxBends, 1, &len);
if (root->right) // if right subtree exists
maximumBends(root->right, 'r', bends,&maxBends, 1, &len);
cout << len << "\n";
}
return 0;
}输出
4
以上代码的解释
在上述方法中，我们只是遍历所有路径并计算到目前为止找到的弯曲次数，当我们到达路径的末尾，即叶节点时，我们检查到这里的弯曲次数是否大于之前的最大值，如果条件为真，那么我们更新最大弯曲次数，并将路径长度更新为这个新长度，这就是我们的程序的执行过程。
结论
在本教程中，我们解决了一个问题，即查找具有最大弯曲次数的路径长度。我们还学习了这个问题的C++程序以及我们用来解决这个问题的完整方法（常规方法）。我们可以用其他语言（例如C、Java、Python和其他语言）编写相同的程序。希望本教程对您有所帮助。
更新于：2021年11月25日
141 次浏览
广告