資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會科學
時尚研究
法律研究在 C++ 中列印二叉樹中的所有 k 和路徑
本題給出一個二叉樹和一個數字 K，我們需要打印出樹中的所有路徑，這些路徑中節點的和等於 k。
這裡，樹的路徑可以從樹的任何節點開始，在任何節點結束。路徑應該總是從根節點直達葉節點。樹中節點的值可以為正、負或零。
來看一個例子來理解本題 −
K = 5
輸出 −
1 3 1 3 2 1 4
要解決本題，我們將每個節點視為樹的根節點，並從臨時根節點到其他節點找出路徑和為 K。
我們將路徑中的所有節點儲存在向量中，並檢查和值是否為 k。
示例
演示演算法實現的程式 −
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node *left,*right;
Node(int x){
data = x;
left = right = NULL;
}
};
void printPath(const vector<int>& v, int i) {
for (int j=i; j<v.size(); j++)
cout<<v[j]<<"\t";
cout<<"\n";
}
void findKSumPath(Node *root, vector<int>& path, int k) {
if (!root)
return;
path.push_back(root->data);
findKSumPath(root->left, path, k);
findKSumPath(root->right, path, k);
int f = 0;
for (int j=path.size()-1; j>=0; j--){
f += path[j];
if (f == k)
printPath(path, j);
}
path.pop_back();
}
int main() {
Node *root = new Node(1);
root->left = new Node(3);
root->left->left = new Node(1);
root->left->right = new Node(2);
root->right = new Node(4);
root->right->right = new Node(7);
int k = 5;
cout<<"Paths with sum "<<k<<" are :\n";
vector<int> path;
findKSumPath(root, path, k);
return 0;
}輸出
Paths with sum 5 are − 1 3 1 3 2 1 4
更新時間： 2020 年 1 月 22 日
426 次瀏覽
廣告