二叉木とある値の経路(剣指offer+二叉木+再帰)
ツリーと値のパス
参加人数:1261時間制限:1秒空間制限:32768 K 通過率:21.61%ベストレコード:0 ms|0 K(から ニックネームをつけて神馬の最もまじめな情を起こしました)タイトルの説明
ツリーと整数を入力し、ツリー内のノード値と入力整数のすべてのパスを印刷します.パスは、ツリーのルートノードからリーフノードまで続くノードがパスを形成するように定義されます.
タイトルリンク:http://www.nowcoder.com/practice/b736e784e3e34731af99065031301bca?rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
長い間、ルートノードから出発して、私は葉の結点に着くたびにこのパスの和を統計して、もしちょうど求めた値に等しいならば、私はこのパスをvectorの2次元配列の中に入れて、さもなくば彼の親ノードに戻って、そして値をpathから削除して、pop_back();ここでvectorを使うのはstackを使うよりいいです!最後に彼に戻って、もちろん私たちは特判空樹が必要です.
考え方はこうです.肝心なのは書くとき、細部に注意することです.
最近面接の問題をしていて、いろいろな虐待心があって、今日は午後の性格テストをしました.明日また筆記試験があります!
やっと就職難を実感した.そんな純粋な心がないと、acmのように自分の興味のあるものを研究することはできません.
自分が別の自分の満足する仕事を見つけることができることを望んで、私の大学に完璧な句点を描きます.がんばって!
参加人数:1261時間制限:1秒空間制限:32768 K 通過率:21.61%ベストレコード:0 ms|0 K(から ニックネームをつけて神馬の最もまじめな情を起こしました)タイトルの説明
ツリーと整数を入力し、ツリー内のノード値と入力整数のすべてのパスを印刷します.パスは、ツリーのルートノードからリーフノードまで続くノードがパスを形成するように定義されます.
タイトルリンク:http://www.nowcoder.com/practice/b736e784e3e34731af99065031301bca?rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
長い間、ルートノードから出発して、私は葉の結点に着くたびにこのパスの和を統計して、もしちょうど求めた値に等しいならば、私はこのパスをvectorの2次元配列の中に入れて、さもなくば彼の親ノードに戻って、そして値をpathから削除して、pop_back();ここでvectorを使うのはstackを使うよりいいです!最後に彼に戻って、もちろん私たちは特判空樹が必要です.
考え方はこうです.肝心なのは書くとき、細部に注意することです.
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
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) {
vector<vector<int> > ans;
if(!root) return ans;
vector<int> path;
int cnt=0;
FindPath(root,expectNumber,path,cnt,ans);
return ans;
}
void FindPath(TreeNode* root,int expectNumber,vector<int> path,int sum,vector<vector<int> >&ans)
{
sum+=root->val;
path.push_back(root->val);
// ,
if(sum==expectNumber && root->left==NULL && root->right==NULL)
{
/* vector<int>::iterator iter = path.begin();
for(;iter!=path.end();iter++)
printf("%d\t",*iter);
printf("
");*/
ans.push_back(path);
}
//
if(root->left)
{
FindPath(root->left,expectNumber,path,sum,ans);
}
if(root->right)
{
FindPath(root->right,expectNumber,path,sum,ans);
}
//
path.pop_back();
}
};
int main()
{
Solution so;
TreeNode* tr;
TreeNode *T=new TreeNode(10);
tr=T;
TreeNode* p=new TreeNode(5);
tr->left=p;
p=new TreeNode(12);
tr->right=p;
tr=tr->left;
p=new TreeNode(4);
tr->left=p;
p=new TreeNode(7);
tr->right=p;
vector<vector<int> > arr=so.FindPath(T,22);
for(int i=0;i<arr.size();i++)
{
vector<int>::iterator iter = arr[i].begin();
for(;iter!=arr[i].end();iter++)
printf("%d\t",*iter);
printf("
");
}
return 0;
}
/*
:
{10,5,12,4,7},22
:
[[10,5,7],[10,12]]
*/
最近面接の問題をしていて、いろいろな虐待心があって、今日は午後の性格テストをしました.明日また筆記試験があります!
やっと就職難を実感した.そんな純粋な心がないと、acmのように自分の興味のあるものを研究することはできません.
自分が別の自分の満足する仕事を見つけることができることを望んで、私の大学に完璧な句点を描きます.がんばって!