import java.util.Stack;

public class SumPath {

    public class BinaryTreeNode{

        int m_nValue;

        BinaryTreeNode m_nLeft;

        BinaryTreeNode m_nRight;

    }

    public BinaryTreeNode createBinaryTree(int[] pre,int start,int[] ord,int end,int length){

        if(pre==null||ord==null||pre.length!=ord.length||length<=0)

            return null;

        int value=pre[start];

        BinaryTreeNode root=new BinaryTreeNode();

        root.m_nValue=value;

        root.m_nLeft=root.m_nRight=null;

        if(length==1){

            if(pre[start]==ord[end])

                return root;

            else

                throw new RuntimeException("inVaild put!");

        }

        //在中序遍历的序列中找到根节点

        int i=0;

        for(;i<length;i++){

            if(ord[end-i]==value)

                break;

        }

        if(i==length)

            throw new RuntimeException("inVaild put!");

        int left=length-i-1;

        int right=i;

        if(left>0)

            root.m_nLeft=createBinaryTree(pre,start+1,ord,end-i-1,length-i-1);

        if(right>0)

            root.m_nRight=createBinaryTree(pre,start+length-i,ord,end,i);

        return root;

    }

    public void sumPath(BinaryTreeNode root,int sum){

        if(root==null)

            return;

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

        findPath(root,sum,stack);

    }

    public void findPath(BinaryTreeNode root, int sum, Stack<Integer> stack) {

        if(root==null)

            return;

        //当遍历到叶子节点的时候，计算整个路径上的值是否为指定的值

        if(root.m_nLeft==null&&root.m_nRight==null)

        {

            if(root.m_nValue==sum){

                for(int i:stack)

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

            System.out.println(root.m_nValue);

            }

        }

        stack.push(root.m_nValue);
        //sum-root.m_nValue减去父节点的值，直到叶子几点，如果叶子节点等于剩下的值，那么就遍历成功。

        if(root.m_nLeft!=null)

        findPath(root.m_nLeft,sum-root.m_nValue,stack);

        if(root.m_nRight!=null)

        findPath(root.m_nRight,sum-root.m_nValue,stack);

        stack.pop();

    }

    public static void main(String[] args){

        int[] a={3,4,6,8,5,7,9};

        int[] b={6,4,8,3,7,5,9};

        SumPath sumPath=new SumPath();

        BinaryTreeNode pHead=sumPath.createBinaryTree(a, 0, b, 6, a.length);

        sumPath.sumPath(pHead, 15);

    }

}