題目描述

????給定一個(gè)二叉樹和一個(gè)整數(shù)状知，打印出二叉樹中和為輸入整數(shù)的所有路徑弥雹。從根節(jié)點(diǎn)開始往下一直到葉節(jié)點(diǎn)所經(jīng)過的節(jié)點(diǎn)形成的一條路徑转捕。

思路分析

????以下圖二叉樹為例，過程分析見表格A：

測試二叉樹

表格A

Java代碼實(shí)現(xiàn)

import java.util.Stack;

/**
 * 在二叉樹中找出所有從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑和為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);
            //如果是葉節(jié)點(diǎn)，并且路徑和等于期望值，則打印路徑
            if(isLeafNode&&currentSum==expectedSum){
                printPath(path);
            }
            
            //如果不是葉節(jié)點(diǎn)周崭，則遍歷其子節(jié)點(diǎn)
            if(root.leftTreeNode!=null){
                findPathInSum(root.leftTreeNode, path, expectedSum, currentSum);
            }
            if(root.rightTreeNode!=null){
                findPathInSum(root.rightTreeNode, path, expectedSum, currentSum);
            }
            
            //返回父節(jié)點(diǎn)之前，在路徑上刪除當(dāng)前節(jié)點(diǎn)
            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;
    }
}