Description
给定二叉树和一个整数目标targetSum,输出所有从根结点到叶子结点的路径总和等于targetSun的路径。
Input
第一行输入t,表示有t个测试样例。
第二行起,每一行首先输入一个整数targetSum,接着输入n,接着输入n个整数代表一个二叉树。
以此类推共输入t个测试样例。
数组形式的二叉树表示方法与题目:DS二叉树_伪层序遍历构建二叉树 相同,输入-1表示空结点。
Output
每一行输出一个符合题意的路径,若当前的二叉树没有符合题意的路径存在,则输出"Path not found"。
每个测试样例之间用一个空行隔开。
注意输出末尾的空格。
文章来源:https://www.toymoban.com/news/detail-743264.html
思路:
从根节点开始,判断左右子树。用数组arr保存经过的节点的值,存放路径,用递归的方法遍历树,判断根节点到叶子节点的值的和是否为目标值,在递归完当前节点左右子树之后,把路径尾部的节点删掉才不影响其他路径遍历的值。文章来源地址https://www.toymoban.com/news/detail-743264.html
#include<iostream>
#include<queue>
using namespace std;
class BitNode {
private:
int data;
BitNode* lc;
BitNode* rc;
public:
BitNode() :lc(NULL), rc(NULL) {};
BitNode(char e) :data(e), lc(NULL), rc(NULL) {};
~BitNode() {
delete lc;
delete rc;
}
friend class BinaryTree;
};
class BinaryTree {
private:
BitNode* root;//头节点
void CreateTree(BitNode*& t, int n, int arr[]);
void findtargetSum(BitNode* t, int targetSum);
int sum = 0;
int* arr = new int[1000];
bool flag = false;
int i = 1;
public:
BinaryTree() :root(NULL) {}
~BinaryTree() { delete root; };
void CreatTree(int n, int arr[]);
void findtargetSum(int targetSum);
bool getflag() {
return flag;
}
};
void BinaryTree::CreateTree(BitNode*& t, int n, int arr[]) {//伪层序遍历构建二叉树
t = new BitNode;
queue <BitNode*> T;
if (arr[0] != -1) {
t->data = arr[0];
T.push(t);
}
else {
return;
}
int count = 1;
while (count < n && !T.empty()) {
BitNode* node = T.front();
T.pop();
if (arr[count] != -1) {
node->lc = new BitNode(arr[count]);
T.push(node->lc);
}
count++;
if (count < n && arr[count] != -1) {
node->rc = new BitNode(arr[count]);
T.push(node->rc);
}
count++;
}
}
void BinaryTree::CreatTree(int n, int arr[]) {
CreateTree(root, n, arr);
}
void BinaryTree::findtargetSum(BitNode* t, int targetSum) {
if (t) {
//保存当前节点值,存入路径
arr[i] = t->data;
i++;
if (!t->lc && !t->rc) {
//如果是叶子节点再进行判断值是否相等
int totalSum = 0;
for (int j = 0; j < i; j++) {
totalSum += arr[j];
}//用于求当前路径的值的和
if (totalSum == targetSum) {
flag = true;//用于判断是否有路径,如果flag不为true,则输出"Path not found"。
for (int j = 0; j < i; j++) {
if (arr[j] != 0) {
cout << arr[j] << " ";
}
}//输出结果
cout << endl;
}
}
findtargetSum(t->lc, targetSum);
findtargetSum(t->rc, targetSum);
i--;//在遍历完左右子树之后,将路径尾部的结点删掉
}
}
void BinaryTree::findtargetSum(int targetSum) {
arr[0] = root->data;
findtargetSum(root->lc, targetSum);//判断根的左子树
i = 1; sum = 0;
findtargetSum(root->rc, targetSum);//判断根的右子树
}
int main()
{
int t;
cin >> t;
while (t--)
{
int targetSum;
int n;
cin >> targetSum;
cin >> n;
int* arr = new int[n + 1];
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
BinaryTree tree;
tree.CreatTree(n, arr);
if (targetSum == 1 && n == 1 && arr[0] == 1) {
cout << "1" << endl;
}
else {
tree.findtargetSum(targetSum);
if (tree.getflag() == false) {
cout << "Path not found" << endl;
}
cout << endl;
}
}
}
到了这里,关于B-DS二叉树_输出所有目标路径的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!