Chinaunix首页 | 论坛 | 博客
  • 博客访问: 407446
  • 博文数量: 101
  • 博客积分: 2207
  • 博客等级: 大尉
  • 技术积分: 2508
  • 用 户 组: 普通用户
  • 注册时间: 2011-04-19 20:45
文章分类

全部博文(101)

文章存档

2013年(15)

2012年(86)

我的朋友

分类: C/C++

2012-09-24 15:33:24

题目:输入一个整数和一棵二元树。
从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。
打印出和与输入整数相等的所有路径。
例如 输入整数22和如下二元树
10
/ /
5 12
/ /
4 7
则打印出两条路径:10, 12和10, 5, 7。

 点击(此处)折叠或打开

  1. #include <iostream>
  2. #include <vector>

  3. struct Node
  4. {
  5.     int data_;
  6.     Node* left;
  7.     Node* right;

  8.     Node(int data)
  9.     {
  10.         data_ = data;
  11.         left = right = NULL;
  12.     }
  13. };

  14. void FindPath(Node* pTreeNode,int expectedSum, std::vector<int>& path,int& currentSum)
  15. {
  16.     if (pTreeNode)
  17.     {
  18.         currentSum += pTreeNode->data_;
  19.         path.push_back(pTreeNode->data_);
  20.         bool isLeaf = (!pTreeNode->left && !pTreeNode->right);
  21.         if (currentSum == expectedSum && isLeaf)
  22.         {
  23.             std::vector<int>::iterator iter = path.begin();
  24.             for (;iter != path.end(); ++iter)
  25.             {
  26.                 std::cout << *iter << " ";
  27.             }
  28.             std::cout << "\n" << std::endl;
  29.         }

  30.         if (pTreeNode->left)
  31.         {
  32.             FindPath(pTreeNode->left,expectedSum,path,currentSum);
  33.         }
  34.         if (pTreeNode->right)
  35.         {
  36.             FindPath(pTreeNode->right,expectedSum,path,currentSum);
  37.         }
  38.         // when we finish visiting a node and return to its parent node,
  39.         // we should delete this node from the path and
  40.         // minus the node's value from the current sum
  41.         currentSum -= pTreeNode->data_;
  42.         path.pop_back();
  43.     }
  44. }

  45. int main()
  46. {
  47.     struct Node *root = new Node(10);
  48.     root->left = new Node(5);
  49.     root->right = new Node(12);

  50.     root->left->left = new Node(4);
  51.     root->left->right = new Node(7);

  52.     std::vector<int> path;
  53.     int currentSum = 0;
  54.     FindPath(root,22,path,currentSum);

  55. }

阅读(998) | 评论(0) | 转发(3) |
给主人留下些什么吧!~~