-
Notifications
You must be signed in to change notification settings - Fork 0
/
PathInTree.cpp
55 lines (41 loc) · 1.39 KB
/
PathInTree.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <stdio.h>
#include <vector>
#include "utils/BinaryTree.h"
void FindPath(BinaryTreeNode* pRoot, int expectedSum, std::vector<int>& path, int ¤tSum);
void FindPath(BinaryTreeNode* pRoot, int expectedSum) {
if (pRoot != NULL) {
int currentSum = 0;
std::vector<int> path;
FindPath(pRoot, expectedSum, path, currentSum);
}
}
void FindPath(BinaryTreeNode* pRoot, int expectedSum, std::vector<int>& path, int ¤tSum) {
currentSum += pRoot->m_nValue;
path.push_back(pRoot->m_nValue);
bool isLeaf = pRoot->m_pLeft == NULL && pRoot->m_pRight == NULL;
if (isLeaf && currentSum == expectedSum) {
printf("A path is found: ");
std::vector<int>::iterator iter = path.begin();
for(; iter != path.end(); iter++)
printf("%d ", *iter);
printf("\n");
}
if (pRoot->m_pLeft != NULL)
FindPath(pRoot->m_pLeft, expectedSum, path, currentSum);
if (pRoot->m_pRight != NULL)
FindPath(pRoot->m_pRight, expectedSum, path, currentSum);
//TODO
currentSum -= pRoot->m_nValue;
path.pop_back();
}
int main() {
BinaryTreeNode* pNode10 = CreateBinaryTreeNode(10);
BinaryTreeNode* pNode5 = CreateBinaryTreeNode(5);
BinaryTreeNode* pNode12 = CreateBinaryTreeNode(12);
BinaryTreeNode* pNode4 = CreateBinaryTreeNode(4);
BinaryTreeNode* pNode7 = CreateBinaryTreeNode(7);
ConnectTreeNodes(pNode10, pNode5, pNode12);
ConnectTreeNodes(pNode5, pNode4, pNode7);
FindPath(pNode10, 22);
return 0;
}