摘自：http://www.cnblogs.com/qi09/archive/2011/05/24/2055643.html

4.在二元树中找出和为某一值的所有路径 
题目：输入一个整数和一棵二元树。 
从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。 
打印出和与输入整数相等的所有路径。 
例如输入整数22 和如下二元树 
10 
/ \ 
5 12 
/\ 
4 7 
则打印出两条路径：10, 12 和10, 5, 7。 
二元树节点的数据结构定义为： 
struct BinaryTreeNode // a node in the binary tree 
{ 
int m_nValue; // value of node 
BinaryTreeNode *m_pLeft; // left child of node 
BinaryTreeNode *m_pRight; // right child of node 
};

  1. /**
  2. *
  3. */
  4. package com.lhp;
  5. import java.util.ArrayList;
  6. import java.util.List;
  7. /**
  8. 4.在二元树中找出和为某一值的所有路径
  9. 题目：输入一个整数和一棵二元树。
  10. 从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。
  11. 打印出和与输入整数相等的所有路径。
  12. 例如输入整数22 和如下二元树
  13. 10
  14. / \
  15. 5 12
  16. /\
  17. 4 7
  18. 则打印出两条路径：10, 12 和10, 5, 7。
  19. 二元树节点的数据结构定义为：
  20. struct BinaryTreeNode // a node in the binary tree
  21. {
  22. int m_nValue; // value of node
  23. BinaryTreeNode *m_pLeft; // left child of node
  24. BinaryTreeNode *m_pRight; // right child of node
  25. };
  26. */
  27. /**
  28. * 二叉树
  29. */
  30. class BinaryTree {
  31. private BinaryTreeNode root;    // 根
  32. public BinaryTreeNode getRoot() {
  33. return root;
  34. }
  35. public void setRoot(BinaryTreeNode root) {
  36. this.root = root;
  37. }
  38. /**
  39. * 增加子节点
  40. * @param 节点
  41. */
  42. public synchronized void addNode(BinaryTreeNode node) {
  43. if (null == this.root) {
  44. this.root = node;
  45. return;
  46. }
  47. BinaryTreeNode tempNode = this.root;
  48. while (true) {
  49. if (node.getM_nValue() > tempNode.getM_nValue()) {   // 大于父节点
  50. if (null == tempNode.getM_pRight()) {
  51. tempNode.setM_pRight(node);
  52. return;
  53. } else {
  54. tempNode = tempNode.getM_pRight();
  55. continue;
  56. }
  57. } else if (node.getM_nValue() < tempNode.getM_nValue()) {    // 小于父节点
  58. if (null == tempNode.getM_pLeft()) {
  59. tempNode.setM_pLeft(node);
  60. return;
  61. } else {
  62. tempNode = tempNode.getM_pLeft();
  63. continue;
  64. }
  65. } else {    // 等于父节点
  66. return;
  67. }
  68. }
  69. }
  70. /**
  71. * 输出指定路径和大小的所有路径
  72. * @param 路径的和
  73. */
  74. public synchronized void printSumPath(int sumValue) {
  75. printSumPath(this.root, new ArrayList<Integer>(), 0, sumValue);
  76. }
  77. /**
  78. * @param 节点
  79. * @param 路径存储集合
  80. * @param 临时路径的和
  81. * @param 路径的和
  82. */
  83. private void printSumPath(BinaryTreeNode node, List<Integer> path, int tempSum, int sumValue) {
  84. if (null == node) {
  85. return;
  86. }
  87. tempSum += node.getM_nValue();
  88. path.add(node.getM_nValue());
  89. boolean isLeaf = (null == node.getM_pLeft() && null == node.getM_pRight()); // 是否为叶子
  90. if (isLeaf && tempSum == sumValue) {    // 满足
  91. System.out.print("sumPath(" + sumValue + "): ");
  92. for (int i : path) {
  93. System.out.print(i + " ");
  94. }
  95. System.out.println();
  96. }
  97. // 《向左走，向右走》 :-)
  98. printSumPath(node.getM_pLeft(), path, tempSum, sumValue);
  99. printSumPath(node.getM_pRight(), path, tempSum, sumValue);
  100. // 保证递归完成后返回父节点时路径是根结点到父节点的路径，之后遍历父节点的其他子节点，没有则返回到爷爷节点...
  101. path.remove(path.size() - 1);   // 删除当前节点
  102. // 最后补充一下，如果path不是指针而是基本类型的话，这句话就没用了（放在递归调用下面就没用了），算法也废了，比如在这里加入一句tempSum+=XXX;对结果没有任何影响，不会影响递归return时其他函数里的参数
  103. }
  104. /**
  105. * 打印前序遍历
  106. */
  107. public synchronized void print() {
  108. if (null == this.root) {
  109. System.out.print("HashCode: " + this.hashCode() +  "; 空树;");
  110. return;
  111. }
  112. System.out.print("HashCode: " + this.hashCode() +  "; 树: ");
  113. print(this.root);
  114. System.out.println();
  115. }
  116. private void print(BinaryTreeNode node) {
  117. if (null != node) {
  118. System.out.print(node.getM_nValue() + " ");
  119. print(node.getM_pLeft());
  120. print(node.getM_pRight());
  121. }
  122. }
  123. }
  124. /**
  125. * 节点
  126. */
  127. class BinaryTreeNode {
  128. private int m_nValue; // value of node
  129. private BinaryTreeNode m_pLeft; // left child of node
  130. private BinaryTreeNode m_pRight; // right child of node
  131. BinaryTreeNode(int value) {
  132. this.m_nValue = value;
  133. }
  134. public int getM_nValue() {
  135. return m_nValue;
  136. }
  137. public void setM_nValue(int mNValue) {
  138. m_nValue = mNValue;
  139. }
  140. public BinaryTreeNode getM_pLeft() {
  141. return m_pLeft;
  142. }
  143. public void setM_pLeft(BinaryTreeNode mPLeft) {
  144. m_pLeft = mPLeft;
  145. }
  146. public BinaryTreeNode getM_pRight() {
  147. return m_pRight;
  148. }
  149. public void setM_pRight(BinaryTreeNode mPRight) {
  150. m_pRight = mPRight;
  151. }
  152. }
  153. public class Four {
  154. public static void main(String[] args) {
  155. BinaryTree tree = new BinaryTree();
  156. tree.addNode(new BinaryTreeNode(10));
  157. tree.addNode(new BinaryTreeNode(5));
  158. tree.addNode(new BinaryTreeNode(12));
  159. tree.addNode(new BinaryTreeNode(4));
  160. tree.addNode(new BinaryTreeNode(7));
  161. tree.addNode(new BinaryTreeNode(9));
  162. tree.addNode(new BinaryTreeNode(3));
  163. tree.print();
  164. tree.printSumPath(22);
  165. tree.printSumPath(31);
  166. }
  167. }

最新文章

  1. jQuery打造智能提示插件
  2. AJAX提交方法（GET）Demon
  3. LayaAir引擎——（二）
  4. iframe父页面获取子页面的高度
  5. wcf,socket,数据传输方式
  6. openresty 前端开发进阶一之http后端
  7. Mybatis+SpringMVC+Spring整合
  8. JNI基础概念以及原理-2016.01.11
  9. 前端--关于javascript函数
  10. DNS没有生效的几个原因
  11. Masonry的简单使用
  12. jeesz分布式架构集成阿里云oss存储
  13. RobotFramework下的http接口自动化Get Response Status 关键字的使用
  14. （转载记录）Active Directory 灾难恢复
  15. document,element,node方法
  16. 使用Windows API进行串口编程
  17. JavaScript中利用Ajax 实现客户端与服务器端通信（九）
  18. yum常用命令大全
  19. vue实用组件——表格
  20. Swift map filter reduce 使用指南

热门文章

  1. Javascript -- 级联菜单, javascript解析xml文件
  2. BZOJ 3698 XWW的难题：有上下界的最大流
  3. mysql查询结果带上序号
  4. log4j文件的配置
  5. Java基础学习-抽象类
  6. 《Drools7.0.0.Final规则引擎教程》第4章 4.2 no-loop
  7. iOS编译集成linux开源c库的一些记录
  8. mac brew安装使用卸载
  9. 【转载】VC获取MAC地址的4种方法
  10. Java 三大特征之--多态