题目描述

给定一个二叉树和一个值sum，请找出所有的根节点到叶子节点的节点值之和等于sum的路径，
例如：
给出如下的二叉树，sum=22，
5↵ / ↵ 4 8↵ / / ↵ 11 13 4↵ / / ↵ 7 2 5 1
返回
[↵ [5,4,11,2],↵ [5,8,4,5]↵]↵

代码

思路：这题遇到过很多次了，先序遍历

  1. static ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
  2. static ArrayList<Integer> arr = new ArrayList<Integer>();
  3. public static ArrayList<ArrayList<Integer>> pathSum (TreeNode root, int sum) {
  4.         if(root==null)return null;
  5.         preOrder(root,sum,0);
  6.         return list;            
  7.     }
  8.     public static void preOrder(TreeNode root,int sum,int count) {
  9.         if(root!=null) {
  10.             count += root.val;
  11.             arr.add(root.val);
  12.             if(root.left==null&&root.right==null)
  13.             {
  14.                 if(count==sum) {
  15.                     list.add(new ArrayList<Integer>(arr));
  16.                 }
  17.             }
  18.             if(root.left!=null)preOrder(root.left, sum,count);
  19.             if(root.right!=null)preOrder(root.right, sum,count);
  20.         }
  21.         arr.remove(arr.size()-1);    
  22.     }