《剑指offer》Java实现--寻找二叉树中和为指定值的路径

题目描述

    给定一个二叉树和一个整数，打印出二叉树中和为输入整数的所有路径。从根节点开始往下一直到叶节点所经过的节点形成的一条路径。

思路分析

    以下图二叉树为例，过程分析见表格A：

测试二叉树

表格A

Java代码实现

import java.util.Stack;

/**
 * 在二叉树中找出所有从根节点到叶子节点的路径和为sum的所有路径并输出
 * @author Administrator
 * @version 2018/10/12
 */
public class Exe35_FindPathInBTree {

    public static void main(String[] args) {
        
        TreeNode node10=new TreeNode(10);
        TreeNode node5=new TreeNode(5);
        TreeNode node12=new TreeNode(12);
        TreeNode node4=new TreeNode(4);
        TreeNode node7=new TreeNode(7);
        node10.leftTreeNode=node5;
        node10.rightTreeNode=node12;
        node5.leftTreeNode=node4;
        node5.rightTreeNode=node7;
        findPathInSum(node10, new Stack<TreeNode>(), 22, 0);
        
    }
    
    public static void findPathInSum(TreeNode root,Stack<TreeNode> path,int expectedSum,int currentSum) {
        if(root==null) return;
        else {

            path.add(root);
            currentSum+=root.treeVal;
            boolean isLeafNode=(root.leftTreeNode==null&&root.rightTreeNode==null);
            //如果是叶节点，并且路径和等于期望值，则打印路径
            if(isLeafNode&&currentSum==expectedSum){
                printPath(path);
            }
            
            //如果不是叶节点，则遍历其子节点
            if(root.leftTreeNode!=null){
                findPathInSum(root.leftTreeNode, path, expectedSum, currentSum);
            }
            if(root.rightTreeNode!=null){
                findPathInSum(root.rightTreeNode, path, expectedSum, currentSum);
            }
            
            //返回父节点之前，在路径上删除当前节点
            path.pop();
            
        }
    }
    
    private static void printPath(Stack<TreeNode> path){
        for(int i=0;i<path.size();i++){
            System.out.print(path.get(i)+" ");
        }
        System.out.println();
    }

}

class TreeNode{
    int treeVal;
    TreeNode leftTreeNode;
    TreeNode rightTreeNode;
    public TreeNode(int value) {
        this.treeVal=value;
    }
    @Override
    public String toString() {
        return "Node"+treeVal;
    }
}