1 package com.lintcode; 2  3 import java.util.ArrayList; 4 import java.util.Collections; 5 import java.util.Enumeration; 6 import java.util.List; 7  8 import javax.swing.tree.DefaultMutableTreeNode; 9 import javax.swing.tree.TreeNode;10 11 /**12  * 二叉树的路径和13  * 给定一个二叉树，找出所有路径中各节点相加总和等于给定 目标值 的路径。14  * 一个有效的路径，指的是从根节点到叶节点的路径。15  * @author Administrator16  */17 public class Test_002 {18 //    得到所有最下面的子节点，再根据子节点向上遍历得到序列，每个子节点只能有一个父节点，19 //    所以可以得到所有的序列，再判断序列的值是否等于需要的值。20     /**21      * @param args22      */23     public static void main(String[] args) {24         DefaultMutableTreeNode node1 = new DefaultMutableTreeNode(2);25         node1.add(new DefaultMutableTreeNode(2));26         DefaultMutableTreeNode node7 = new DefaultMutableTreeNode(3);27         node7.add(new DefaultMutableTreeNode(6));28         node1.add(node7);29         DefaultMutableTreeNode node2 = new DefaultMutableTreeNode(4);30         DefaultMutableTreeNode top = new DefaultMutableTreeNode(1);31         top.add(node1);32         top.add(node2);33         binaryTreePathSum(top,5);34         for (List<Integer> list : result) {35             System.out.println(list);36         }37     }38     static List<List<Integer>> result = new ArrayList<List<Integer>>();39     /**40      * @param root the root of binary tree41      * @param target an integer42      * @return all valid paths43      */44     public static void binaryTreePathSum(TreeNode root, int target) {45         if (root.getChildCount()!=0) {46             Enumeration nodes = root.children();47             while (nodes.hasMoreElements()) {48                 binaryTreePathSum((TreeNode)nodes.nextElement(),5);49             }50         } else {51             addList(root,new ArrayList<Integer>(), 5);52         }53     }54     55     public static void addList(TreeNode root, List<Integer> temp, int target) {56         List<Integer> list = temp;57         list.add(Integer.parseInt(root.toString()));58         if (root.getParent()!=null) {59             addList(root.getParent(), list, 5);60         } else {61             Collections.sort(list);62             int count = 0;63             for (Integer integer : list) {64                 count+=integer;65             }66             if (count==target) {67                 result.add(list);68             }69         }70     }71 }