二叉樹中和為某一值的路徑

二叉樹中和為某一值的路徑

輸入一顆二叉樹和一個整數，列印出二叉樹中節點值的和為輸入整數的所有路徑。從樹的根節點到樹的葉子節點所經過的節點，形成一條有效路徑。

思路：路徑總是從根節點出發的，因此我們需要選擇先序遍歷。

每訪問一個節點我們把它添加到數組中，觀察數組和是否與期待值相等，是否是葉子節點。

參考代碼：

root@gt:/home/git/Code# ./a.out 10 5 4 7 12 10 5 7 10 12 root@gt:/home/git/Code# cat findpath.cpp #include <iostream>#include <vector>using namespace std;typedef struct BTreeNode{ int value; struct BTreeNode* pleft; struct BTreeNode* pright;}TreeNode;void core(TreeNode* proot,int expect,vector<int> &path,int currentSum){ currentSum += proot->value; path.push_back(proot->value); bool isLeaf = proot->pleft == NULL && proot->pright == NULL; if(currentSum == expect && isLeaf) { for(vector<int>::iterator iter = path.begin();iter != path.end();++iter) cout <<*iter<<" "; cout<<endl; } if(proot->pleft != NULL) core(proot->pleft,expect,path,currentSum); if(proot->pright != NULL) core(proot->pright,expect,path,currentSum); path.pop_back();}void findpath(TreeNode* proot,int expect){ if(proot == NULL) return; vector<int> path; int currentSum = 0; core(proot,expect,path,currentSum);}TreeNode* concore(int* preStart,int* preEnd,int* inStart,int* inEnd){//前序遍歷的地一個元素就是根節點 int rootValue = preStart[0]; TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode)); root->value = rootValue; root->pleft = root->pright = NULL;//在中序遍歷序號中找到根節點的值 int* rootIn = inStart; while(rootIn <= inEnd && *rootIn != rootValue) ++rootIn; int leftLen = rootIn - inStart; int* leftPreEnd = preStart + leftLen; if(leftLen>0) { root->pleft = concore(preStart+1,leftPreEnd,inStart,inStart+leftLen-1); } if(leftLen < preEnd - preStart) { root->pright = concore(leftPreEnd+1,preEnd,rootIn+1,inEnd); } return root;}TreeNode* construct(int* pre,int* in,int len){ if(pre==NULL || in==NULL || len<=0) return 0; return concore(pre,pre+len-1,in,in+len-1);}void preOrder(TreeNode* root){ if(!root) return; cout << root->value << " "; preOrder(root->pleft); preOrder(root->pright);}int main(){ int pre[] = {10,5,4,7,12}; int in[] = {4,5,7,10,12}; TreeNode* proot = construct(pre,in,sizeof(pre)/sizeof(int)); int expect = 22; preOrder(proot); cout << endl; findpath(proot,expect); return 0;}

推薦閱讀：