[검지 offer-Java 버전] 25 두 갈래 나무와 어떤 값의 경로.

    public class _Q25 {

    public void FindPathInTree(BinaryTreeNode<Integer> tree, int expectedSum){
        if(tree == null) return;

        Vector<BinaryTreeNode<Integer>> path = new Vector<>();
        int curSum = 0;

        FindAndPrintPath(tree, expectedSum, curSum, path);
    }

    private void FindAndPrintPath(BinaryTreeNode<Integer> tree, int expectedSum, 
            int curSum, Vector<BinaryTreeNode<Integer>> path){

        if(tree == null) return;

        curSum = curSum + tree.value;
        path.add(tree);

        if(curSum == expectedSum && tree.leftChild == null && tree.rightChild == null){
            for(int i=0; i<path.size(); i++){
                System.out.print(path.get(i).value + " ");
            }
            System.out.println();
        }

        if(tree.leftChild != null) FindAndPrintPath(tree.leftChild, expectedSum, curSum, path);
        if(tree.rightChild != null) FindAndPrintPath(tree.rightChild, expectedSum, curSum, path);

        path.remove(path.size() - 1); //  
    }
    }

    public class _Q25Test extends TestCase {

    _Q25 printTreePath = new _Q25();

    public void test(){
        BinaryTreeNode<Integer> root = new BinaryTreeNode<>();
        BinaryTreeNode<Integer> node1 = new BinaryTreeNode<>();
        BinaryTreeNode<Integer> node2 = new BinaryTreeNode<>();
        BinaryTreeNode<Integer> node3 = new BinaryTreeNode<>();
        BinaryTreeNode<Integer> node4 = new BinaryTreeNode<>();

        root.value = 10;
        node1.value = 5;
        node2.value = 12;
        node3.value = 4;
        node4.value = 7;

        root.leftChild = node1;
        root.rightChild = node2;
        node1.leftChild = node3;
        node1.rightChild = node4;

        node2.leftChild = null; node2.rightChild = null;
        node3.leftChild = null; node3.rightChild = null;
        node4.leftChild = null; node4.rightChild = null;

        printTreePath.FindPathInTree(root, 22);
    }
    }