本文共 3616 字，大约阅读时间需要 12 分钟。

题目描述

输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)

思路：将所有路径遍历一遍，存入ArrayList<ArrayList<Integer>>，原来做的较为复杂，后来想到了优化

原：

import java.util.ArrayList;/**public class TreeNode {    int val = 0;    TreeNode left = null;    TreeNode right = null;    public TreeNode(int val) {        this.val = val;    }}*/public class Solution {    public ArrayList
   
    
     > FindPath(TreeNode root,int target) {        ArrayList
     
      
       > sum = new ArrayList
       
        
         >(); ArrayList
         
          
           > realSum = new ArrayList
           
            
             >(); int temp=0; if(root==null){ return realSum; } ArrayList
             
               array = new ArrayList
              
               (); computePath(root,sum,array); for(ArrayList
               
                 singleArray:sum){ for(int i:singleArray){ temp += i; } if(temp==target){ realSum.add(singleArray); } temp = 0; } return realSum; } public void computePath(TreeNode root,ArrayList
                
                 
                  > sum,ArrayList
                  
                    array){ if(root.left==null&&root.right==null){ array.add(root.val); sum.add(array); return; } else if(root.left!=null&&root.right==null){ array.add(root.val); computePath(root.left,sum,array); } else if(root.left==null&&root.right!=null){ array.add(root.val); computePath(root.right,sum,array); } else if(root.left!=null&&root.right!=null){ array.add(root.val); computePath(root.left,sum,copyArray(array)); computePath(root.right,sum,copyArray(array)); } } public ArrayList
                   
                     copyArray(ArrayList
                    
                      array){ ArrayList
                     
                       newArray = new ArrayList
                      
                       (); for(Integer i:array){ newArray.add(i); } return newArray; }}
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     
    
   

错误解法：

public class Solution {    public ArrayList
   
    
     > FindPath(TreeNode root,int target) {        ArrayList
     
      
       > sum = new ArrayList
       
        
         >(); ArrayList
         
          
           > realSum = new ArrayList
           
            
             >(); int temp=0; if(root==null){ return realSum; } ArrayList
             
               array = new ArrayList
              
               (); computePath(root,sum,array); for(ArrayList
               
                 singleArray:sum){ for(int i:singleArray){ temp += i; } if(temp==target){ realSum.add(singleArray); } temp = 0; } return realSum; } public void computePath(TreeNode root,ArrayList
                
                 
                  > sum,ArrayList
                  
                    array){ if(root.left==null&&root.right==null){ array.add(root.val); sum.add(array); //这里如果不新建ArrayList array移除元素会影响sum array.remove(array.size()-1); return; } else{ array.add(root.val); if(root.left!=null){ computePath(root.left,sum,array); } if(root.right!=null){ computePath(root.right,sum,array); } array.remove(array.size()-1); } }}
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     
    
   

正确解法：

public class Solution {    public ArrayList
   
    
     > FindPath(TreeNode root,int target) {        ArrayList
     
      
       > sum = new ArrayList
       
        
         >(); ArrayList
         
          
           > realSum = new ArrayList
           
            
             >(); int temp=0; if(root==null){ return realSum; } ArrayList
             
               array = new ArrayList
              
               (); computePath(root,sum,array); for(ArrayList
               
                 singleArray:sum){ for(int i:singleArray){ temp += i; } if(temp==target){ realSum.add(singleArray); } temp = 0; } return realSum; } public void computePath(TreeNode root,ArrayList
                
                 
                  > sum,ArrayList
                  
                    array){ if(root.left==null&&root.right==null){ array.add(root.val); sum.add(new ArrayList(array)); array.remove(array.size()-1); return; } else{ array.add(root.val); if(root.left!=null){ computePath(root.left,sum,array); } if(root.right!=null){ computePath(root.right,sum,array); } array.remove(array.size()-1); } }}
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     
    
   

参考内存泄漏内容

import java.util.ArrayList;

import java.util.Vector;

public class dadad {

    static ArrayList v = new ArrayList(10);     public static void main(String[] args) {         //ArrayList v = new ArrayList(10);         for (int i = 1; i<100; i++)         {             Object o = new Object();             v.add(o);             o = null;         }         System.out.println(v.get(0)==null);     false     } }

转载地址：http://euonn.baihongyu.com/