题目:输入一个整数和一棵二元树。
从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。
打印出和与输入整数相等的所有路径。
例如
输入整数22和如下二元树
10
/ /
5 12
/ /
4 7
则打印出两条路径:10, 12和10, 5,
7。
- #include <iostream>
- #include <vector>
- struct Node
- {
- int data_;
- Node* left;
- Node* right;
- Node(int data)
- {
- data_ = data;
- left = right = NULL;
- }
- };
- void FindPath(Node* pTreeNode,int expectedSum, std::vector<int>& path,int& currentSum)
- {
- if (pTreeNode)
- {
- currentSum += pTreeNode->data_;
- path.push_back(pTreeNode->data_);
- bool isLeaf = (!pTreeNode->left && !pTreeNode->right);
- if (currentSum == expectedSum && isLeaf)
- {
- std::vector<int>::iterator iter = path.begin();
- for (;iter != path.end(); ++iter)
- {
- std::cout << *iter << " ";
- }
- std::cout << "\n" << std::endl;
- }
- if (pTreeNode->left)
- {
- FindPath(pTreeNode->left,expectedSum,path,currentSum);
- }
- if (pTreeNode->right)
- {
- FindPath(pTreeNode->right,expectedSum,path,currentSum);
- }
- // when we finish visiting a node and return to its parent node,
- // we should delete this node from the path and
- // minus the node's value from the current sum
- currentSum -= pTreeNode->data_;
- path.pop_back();
- }
- }
- int main()
- {
- struct Node *root = new Node(10);
- root->left = new Node(5);
- root->right = new Node(12);
- root->left->left = new Node(4);
- root->left->right = new Node(7);
- std::vector<int> path;
- int currentSum = 0;
- FindPath(root,22,path,currentSum);
- }
阅读(219) | 评论(0) | 转发(0) |