資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告