題目描述

輸入一顆二叉樹(shù)的跟節(jié)點(diǎn)和一個(gè)整數(shù)，打印出二叉樹(shù)中結(jié)點(diǎn)值的和為輸入整數(shù)的所有路徑。路徑定義為從樹(shù)的根結(jié)點(diǎn)開(kāi)始往下一直到葉結(jié)點(diǎn)所經(jīng)過(guò)的結(jié)點(diǎn)形成一條路徑。

解題思路

要求一路徑的和，那么必然終止條件為葉子結(jié)點(diǎn)，從根結(jié)點(diǎn)出發(fā)，從左往右，每條路徑的和都與給定的值比較，自然能求出。
但往往二叉樹(shù)的題，都會(huì)用到遞歸，本身是二叉樹(shù)，那么子樹(shù)必定為二叉樹(shù)，如果找到規(guī)律？？
我們可以這樣想，遞歸一次，舊調(diào)用系統(tǒng)棧一次保存數(shù)據(jù)。既然要路徑上的所有結(jié)點(diǎn)的和等于給定的值，就說(shuō)明給定的值減去路徑的和等于0。我們就不難想到，每次遞歸減去當(dāng)前根結(jié)點(diǎn)的值，一直到葉子結(jié)點(diǎn)，如果最后的值等于葉子結(jié)點(diǎn)的值那不就正好可以求解此題。
我們要考慮特殊情況，如果二叉樹(shù)只有一個(gè)結(jié)點(diǎn)，并恰巧那個(gè)結(jié)點(diǎn)的值等于給定的值呢？？所以，每回減去當(dāng)前根結(jié)點(diǎn)的值前，先判斷是否相等，再減去。
如果到葉子結(jié)點(diǎn)不相等，那么就往上走，再往右邊走。
有了上述思路，就不難寫出如下代碼

代碼實(shí)現(xiàn)

class Solution {vector<vector<int>> result;vector<int> path; public:void find(TreeNode* root,int expectnum){if(root == NULL)return ;path.push_back(root->val);if(!root->left&&!root->right&& expectnum == root->val)result.push_back(path);else{if(root->left)find(root->left,expectnum-root->val);if(root->right)find(root->right,expectnum-root->val);}path.pop_back();}vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {find(root,expectNumber);return result;} };

總結(jié)

以上是生活随笔為你收集整理的【剑指offer】_10二叉树和为某一路径值的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。