首页 > 代码库 > 在二元树中找出和为某一值的所有路径
在二元树中找出和为某一值的所有路径
题目:输入一个整数和一棵二元树。 从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。 打印出和与输入整数相等的所有路径。
例如输入整数 22 和如下二元树 :
10
/
5 12
/\
47
则打印出两条路径:10, 12 和 10, 5, 7。
1 package data.structure.exercise; 2 3 import java.util.LinkedList; 4 5 6 public class BinaryTree extends BinarySearchTree{ 7 8 LinkedList<TreeNode> pathStack = new LinkedList<TreeNode>(); 9 10 public BinaryTree(int root){ 11 12 super(root); 13 } 14 15 16 public void findPathSum(int sum){ 17 if(this.getRoot() == null){ 18 return; 19 } 20 dfs(this.getRoot(), sum); 21 } 22 23 private void dfs(TreeNode node, int current){ 24 if(node == null){ 25 return; 26 } 27 28 pathStack.push(node);; 29 30 if(node.getLnode() == null && node.getRnode() == null){ 31 //being a path and calculate the sum 32 if(current == node.getValue()){ 33 printPath(pathStack); 34 } 35 }else{ 36 //traverse left node 37 if(node.getLnode() !=null){ 38 39 dfs(node.getLnode(), current - node.getValue()); 40 } 41 42 //traverse right node 43 if(node.getRnode() !=null){ 44 dfs(node.getRnode(), current - node.getValue()); 45 } 46 } 47 pathStack.pop(); 48 49 } 50 51 private void printPath(LinkedList<TreeNode> pathStack){ 52 for(TreeNode node:pathStack){ 53 System.out.print(node.toValueString()+"="); 54 } 55 System.out.println(); 56 } 57 58 public static void main(String[] args){ 59 BinaryTree tree = new BinaryTree(10); 60 tree.insert(5); 61 tree.insert(12); 62 tree.insert(4); 63 tree.insert(7); 64 65 66 System.out.println("root.left: "+ tree.getRoot().getLnode().toString()); 67 68 tree.findPathSum(22); 69 } 70 }
BinarySearchTree参考上篇博文
在二元树中找出和为某一值的所有路径
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。