题目：有一个二叉树如下图所示，要求编程找出所有从根节点到叶节点路径总和等于22的路径。
5
/
4 8
/ /
11 13 4
/ /
7 2 5 1
#include#include #include using namespace std; const int SUM = 22; struct node { int value; struct node *left_child = nullptr, *right_child = nullptr; string paths = "";//父节点以上所有节点的value转string后拼接，split by ' ' int sum = 0;//父节点以上所有节点的value加和 }; struct node *new_node(int value) { struct node *p = new struct node; p->value = value; return p; } struct node *add_children(int parent_value, struct node *left_child, struct node *right_child) { struct node *parent = new struct node; parent->value = parent_value; parent->left_child = left_child; parent->right_child = right_child; return parent; } // 通过遍历二叉树的方式（这里采用中序遍历，当然采用前序遍历和后序遍历也可以），当遍历到叶节点的时候，判断该条路径是否符合条件 void traverse_tree(struct node *parent) { if (parent == nullptr) return; if (parent->left_child) { parent->left_child->paths = parent->paths + " " + to_string(parent->value); parent->left_child->sum = parent->sum + parent->value; traverse_tree(parent->left_child); } if (parent->left_child == nullptr && parent->right_child == nullptr) // 判断当前是否为叶节点 { // 判断路径上的节点总和是否等于SUM if (parent->sum + parent->value == SUM) cout << "找到一条路径：" << parent->paths << " " << parent->value << endl; } if (parent->right_child) { parent->right_child->paths = parent->paths + " " + to_string(parent->value); parent->right_child->sum = parent->sum + parent->value; traverse_tree(parent->right_child); } } int main() { struct node *binary_tree = nullptr; // 生成左子树 struct node *left_child = new_node(7); struct node *right_child = new_node(2); struct node *parent = nullptr; parent = add_children(11, left_child, right_child); parent = add_children(4, parent, nullptr); binary_tree = add_children(5, parent, nullptr); // 生成右子树 left_child = new_node(5); right_child = new_node(1); parent = add_children(13, left_child, right_child); parent = add_children(8, parent, new_node(4)); binary_tree->right_child = parent; // 找到目标和等于SUM的路径 traverse_tree(binary_tree); return 0; }
程序运行得到的结果为：
找到一条路径： 5 4 11 2
也许这里给出的程序实现不是最好的，但这也算是可行的一种解法吧！
如果题目再修改一下，变为“编程找出所有途经节点路径总和等于22的路径。”，程序的实现可以是下面这样子：
#include#include using namespace std; const int SUM = 22; struct node { int value; struct node *parent = nullptr, *left_child = nullptr, *right_child = nullptr; }; struct node *new_node(int value) { struct node *p = new struct node; p->value = value; return p; } void add_children(struct node *parent, struct node *left_child, struct node *right_child) { if (left_child) { parent->left_child = left_child; left_child->parent = parent; } if (right_child) { parent->right_child = right_child; right_child->parent = parent; } } struct node *add_children(int parent_value, struct node *left_child, struct node *right_child) { struct node *parent = new struct node; parent->value = parent_value; add_children(parent, left_child, right_child); return parent; } // 通过遍历二叉树的方式（这里采用中序遍历，当然采用前序遍历和后序遍历也可以） void traverse_tree(struct node *parent) { if (parent == nullptr) return; traverse_tree(parent->left_child); // 从当前节点往父节点回溯，判断该路径上的节点总和是否等于SUM；如果不等于，继续回溯，直到根节点 string paths = ""; int sum = 0; struct node *p = parent; while (p) { paths = to_string(p->value) + " " + paths; sum += p->value; if (sum == SUM) { cout << "找到一条路径：" << paths << endl; break; } p = p->parent; } traverse_tree(parent->right_child); } int main() { struct node *binary_tree = nullptr; // 生成左子树 struct node *left_child = new_node(7); struct node *right_child = new_node(2); struct node *parent = nullptr; parent = add_children(11, left_child, right_child); parent = add_children(4, parent, nullptr); binary_tree = add_children(5, parent, nullptr); // 生成右子树 left_child = new_node(5); right_child = new_node(1); parent = add_children(13, left_child, right_child); parent = add_children(8, parent, new_node(4)); add_children(binary_tree, nullptr, parent); // 找到目标和等于SUM的路径 traverse_tree(binary_tree); return 0; }
程序运行的结果为：
找到一条路径：4 11 7
找到一条路径：5 4 11 2
找到一条路径：8 13 1
对这道题，如果你有更好的解法，欢迎在下方留言，一起讨论。
