大学IT网 - 最懂大学生的IT学习网站! QQ资料交流群:367606806
当前位置:大学IT网 > Java技巧 > 二叉树中和为某一值的路径

二叉树中和为某一值的路径

关键词:二叉树路径二叉树中和为某一值的路径  阅读(631) 赞(16)

[摘要]本文主要是对二叉树中和为某一值的路径的讲解,希望对大家学习二叉树中和为某一值的路径有所帮助。

  * 二叉树中和为某一值的路径

  从树的根节点开始往下一直到叶结点所经过的结点形成的路径

  * @author Q.Yuan  *

  */public class BinaryTreePath {

  private Scanner scanner = new Scanner(System.in);

  //先序建立二叉树,测试数据10 5 4 # # 7 # # 12 # #

  public BTreeNode createTree(BTreeNode root){

  String data = scanner.next();

  if(data.equals("#"))

  return null;

  root = new BTreeNode();

  root.data = Integer.valueOf(data);

  root.left = createTree(root.left);

  root.right = createTree(root.right);

  return root;

  }

  /**

  *

  * @param root  树的根节点

  * @param sum   当前路径之和

  * @param stack 存放路径上结点的值

  * @param num   求的路径和

  */

  public void printPath(BTreeNode root,int sum,Stack<Integer> stack,int num){

  if(root != null){

  sum = sum + root.data;

  stack.push(root.data);

  printPath(root.left, sum, stack, num);

  printPath(root.right, sum, stack, num);

  if(sum == num && root.left == null && root.right == null){

  for(int i:stack){

  System.out.print(i+" ");

  }

  System.out.println();

  }

  stack.pop();

  }

  }

  public static void main(String[] args) {

  BinaryTreePath btp = new BinaryTreePath();

  BTreeNode root = null;

  root = btp.createTree(root);

  Stack<Integer> stack = new Stack<Integer>();

  int num = 22;

  int sum = 0;

  btp.printPath(root, sum, stack, num);

  } } //树的结构 class BTreeNode{

  Integer data;

  BTreeNode left;

  BTreeNode right;

  }



相关评论