B-DS二叉树_输出所有目标路径_ds b-树构建及查找

Description

给定二叉树和一个整数目标targetSum，输出所有从根结点到叶子结点的路径总和等于targetSun的路径。

Input

第一行输入t，表示有t个测试样例。

第二行起，每一行首先输入一个整数targetSum，接着输入n，接着输入n个整数代表一个二叉树。

以此类推共输入t个测试样例。

数组形式的二叉树表示方法与题目：DS二叉树_伪层序遍历构建二叉树 相同，输入-1表示空结点。

Output

每一行输出一个符合题意的路径，若当前的二叉树没有符合题意的路径存在，则输出"Path not found"。

每个测试样例之间用一个空行隔开。

注意输出末尾的空格。

 思路：

从根节点开始，判断左右子树。用数组arr保存经过的节点的值，存放路径，用递归的方法遍历树，判断根节点到叶子节点的值的和是否为目标值，在递归完当前节点左右子树之后，把路径尾部的节点删掉才不影响其他路径遍历的值。

#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;
		}
	}
}