首页 > 代码库 > 编程思路总结——递归
编程思路总结——递归
1. 二叉树中和为某一值的路径
路径：从树的根节点到叶子节点经过的节点形成的路径，例如途中（10，5，4），（10，5，7），（10，12）
满足和为22的路径有（10，5，7）、（10，12）
参考代码
void FindPath(TreeNode *root, vector<TreeNode> &vec, int cur, int aim){ if (root == NULL) return; vec.push_back(*root); cur += root->val; bool IsLeft = ((root->left == NULL) && (root->right == NULL)); if (cur == aim && IsLeft) { for (vector<TreeNode>::iterator beg = vec.begin(); beg != vec.end(); ++beg) cout << beg->val << " "; cout << endl; } if (root->left != NULL) FindPath(root->left, vec, cur, aim); if (root->right != NULL) FindPath(root->right, vec, cur, aim); vec.pop_back();}void FindPath(TreeNode *root, int aim){ if (root == NULL) return; vector<TreeNode> vec; FindPath(root, vec, 0, aim);}
测试
#include <iostream>#include <vector>using namespace std;struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int v) : val(v), left(NULL), right(NULL) {};};void FindPath(TreeNode *root, vector<TreeNode> &vec, int cur, int aim){ if (root == NULL) return; vec.push_back(*root); cur += root->val; bool IsLeft = ((root->left == NULL) && (root->right == NULL)); if (cur == aim && IsLeft) { for (vector<TreeNode>::iterator beg = vec.begin(); beg != vec.end(); ++beg) cout << beg->val << " "; cout << endl; } if (root->left != NULL) FindPath(root->left, vec, cur, aim); if (root->right != NULL) FindPath(root->right, vec, cur, aim); vec.pop_back();}void FindPath(TreeNode *root, int aim){ if (root == NULL) return; vector<TreeNode> vec; FindPath(root, vec, 0, aim);}int main(){ TreeNode *root = new TreeNode(10); TreeNode *p1 = new TreeNode(5); TreeNode *p2 = new TreeNode(12); TreeNode *p3 = new TreeNode(4); TreeNode *p4 = new TreeNode(7); root->left = p1; root->right = p2; p1->left = p3; p1->right = p4; FindPath(root, 22);}
编程思路总结——递归
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。