《剑指offer》二叉树中和为某一值的路径

题目链接：?rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

题目描述输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

思路

我们从根结点开始一级一级往下搜，每次搜索都将结点压入路径之中，然后判断这个结点是否为叶子结点，，如果到达叶子结点，就判断这条路径的和是否已经满足了条件，满足条件的话就将这条路径保存起来。

一旦到达底层，我们还需要一层层回溯，所以我们需要用到深搜回溯的特性。

/*struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int x) :val(x), left(NULL), right(NULL) {}};*/class Solution{public:vector<vector<int> > FindPath(TreeNode* root,int expectNumber){if(root==nullptr) return ans;int sum = 0;vector<int> path;Find(root,path,sum,expectNumber);return ans;}void Find(TreeNode *root,vector<int> path,int sum,int expectNumber){sum+=root->val;path.push_back(root->val);bool isLeaf = (root->left==nullptr && root->right==nullptr);if(sum==expectNumber && isLeaf){ans.push_back(path);}if(root->left!=nullptr)Find(root->left,path,sum,expectNumber);if(root->right!=nullptr)Find(root->right,path,sum,expectNumber);path.pop_back();}private:vector<vector<int> > ans;};

积极思考造成积极人生，消极思考造成消极人生。

相关文章：

你感兴趣的文章：

标签云：