IT公司100题-4-在二元树中找出和为某一值的所有路径

问题描述：

输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。

例如输入整数30和如下二元树

14

/ \

5 16

/ \

3 11

则打印出两条路径：14, 16 和14, 5, 11。

二元树节点的数据结构定义为:

typedef struct BSTree {    int data;
    BSTree* left;
    BSTree* right;
} tree_node;

在遍历树的过程中，使用stack保存所走过的路径。如果当前节点为叶子节点，并且路径和等于输入的整数，则输出路径。如果当前节点不是叶子节点，则递归的访问它的孩子节点。在回溯的过程中，注意路径的出栈。

代码实现：

package oschina.mianshi;
/**
 * @project: oschina
 * @filename: IT3.java
 * @version: 0.10
 * @author: JM Han
 * @date: 14:59 2015/10/22
 * @comment: Test Purpose
 * @result:
 */

import java.util.Stack;

import static tool.util.*;

class BSTree3{
   class BSTreeNode{
      BSTreeNode(int x, BSTreeNode lt, BSTreeNode rt){
         value = x;
         left = lt;
         right = rt;
      }
      int value;
      BSTreeNode left;
      BSTreeNode right;
   }

   private BSTreeNode root;
   private int currentSum;
   private Stack<Integer> path;

   public BSTree3(){
      root = null;
      currentSum = 0;
      path = new Stack<Integer>();
   }

   public void insert(int value){
      root = insert(root, value);
   }

   private BSTreeNode insert(BSTreeNode t, int x){
      if(null == t)
         return new BSTreeNode(x, null, null);
      if(t.value > x)
         t.left = insert(t.left, x);
      else if(t.value < x)
         t.right = insert(t.right, x);
      else
         ;//duplicate
      return t;
   }

   public void findPath(int expectSum){
      findPath(root, expectSum);
   }

   private void findPath(BSTreeNode t, int expectSum){
      if(null == t)
         return;

      currentSum += t.value;
      path.push(t.value);

      boolean isLeaf = (t.left == null && t.right == null);

      if(isLeaf && currentSum == expectSum){
         printGenericColection(path);
      }

      if(null != t.left)
         findPath(t.left, expectSum);
      if(null != t.right)
         findPath(t.right, expectSum);

      currentSum -= t.value;
      path.pop();
   }
}

public class IT3 {
   public static void main(String[] args) {
      BSTree3 bsTree = new BSTree3();
      bsTree.insert(14);
      bsTree.insert(5);
      bsTree.insert(16);
      bsTree.insert(3);
      bsTree.insert(11);
      bsTree.findPath(30);
   }
}

代码输出:

14
5
11
14
16

IT公司100题-4-在二元树中找出和为某一值的所有路径

原文：http://my.oschina.net/jimmyhan/blog/520689