【題目】

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

For example:
Given the below binary tree and?sum = 22, 5/ \4 8/ / \11 13 4/ \ / \7 2 5 1

return

[[5,4,11,2],[5,8,4,5] ]

【分析】

題目要求求出所有路徑結果。在求出左子樹滿足結果時，不能return，而是繼續求右子樹。

每到一個葉子節點判斷是否滿足結果，如果滿足添加路徑集合paths中，如果不能滿足結果，把該節點從路徑path中刪除。

【代碼】

/********************************* * 日期：2015-01-02 * 作者：SJF0115 * 題目: 113.Path Sum II * 來源：https://oj.leetcode.com/problems/path-sum-ii/ * 結果：AC * 來源：LeetCode * 博客： * 時間復雜度：O(n) * 空間復雜度：O(logn) **********************************/ #include <iostream> #include <queue> #include <vector> using namespace std;// 二叉樹節點 struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {} };class Solution { public:vector<vector<int> > pathSum(TreeNode *root, int sum) {// 一條路徑vector<int> path;// 多條路徑vector<vector<int> > paths;if (root == NULL){return paths;}//ifpathSum(root,sum,path,paths);return paths;} private:void pathSum(TreeNode *root, int sum,vector<int>& path,vector<vector<int> >& paths) {// 當前節點添加到路徑中path.push_back(root->val);int cur = sum - root->val;// 判斷是否找到一條root-to-leaf路徑和等于sumif(root->left == NULL && root->right == NULL && cur == 0){paths.push_back(path);}//if// left sub-treeif(root->left){pathSum(root->left,cur,path,paths);// 回溯上層節點刪除當前節點path.pop_back();}//if// right sub-treeif(root->right){pathSum(root->right,cur,path,paths);// 回溯上層節點刪除當前節點path.pop_back();}//if} }; // 創建二叉樹 TreeNode* CreateTreeByLevel(vector<int> num){int len = num.size();if(len == 0){return NULL;}//ifqueue<TreeNode*> queue;int index = 0;// 創建根節點TreeNode *root = new TreeNode(num[index++]);// 入隊列queue.push(root);TreeNode *p = NULL;while(!queue.empty() && index < len){// 出隊列p = queue.front();queue.pop();// 左節點if(index < len && num[index] != -1){// 如果不空創建一個節點TreeNode *leftNode = new TreeNode(num[index]);p->left = leftNode;queue.push(leftNode);}index++;// 右節點if(index < len && num[index] != -1){// 如果不空創建一個節點TreeNode *rightNode = new TreeNode(num[index]);p->right = rightNode;queue.push(rightNode);}index++;}//whilereturn root; }int main() {Solution solution;// -1代表NULLvector<int> num = {5,4,8,11,-1,13,4,7,2,-1,-1,5,1};TreeNode* root = CreateTreeByLevel(num);vector<vector<int> > paths = solution.pathSum(root,22);for(int i = 0;i < paths.size();i++){for(int j = 0;j < paths[i].size();j++){cout<<paths[i][j]<<" ";}cout<<endl;} }

總結

以上是生活随笔為你收集整理的[LeetCode]113.Path Sum II的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。