剑指offer34

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

1. list容器(数组线性表)：List<List<Integer>> list=new ArrayList<>()

• list.add(obj)向尾部添加元素,list.add(int index,Object obj)向index索引位置添加元素。特别要注意的是，add()方法加入的是对象的地址，要加入不同对象需要new新的对象。add()允许添加重复元素。
• list.remove(int i)删除索引i位置的元素，可以这样子写remove(list.indexOf(Object a))。另一种是remove(Object a)，如果是对象引用则直接传对象引用作为参数，若传的是基本类型，则需要先转化成包装类remove(Integer.valueOf(250))。
• list.size()获取list的长度
• list.get(int i)返回索引下标为i的元素
• list.contains(int i)容器中含有i则返回true,可以用来去重。
• List<object> list=new ArrayList<>(Arrays.asList(object a，object b，object c...))：一种初始化写法

2. 注意找到正确的路径记录进list时，若直接执行list.add(path) ，则是将 path 对象加入了list ；后续 path 改变时，list 中的 path 对象也会随之改变。因此每次添加一个新的容器进入到容器，都要新实例化一个新的容器。list.add(new ArrayList<>(path)),相当于复制了一个path加入到list。

3. 深搜过程中，如果是叶子结点则判断当前路径能不能加入到list当中然后退出当前搜索，否则继续遍历左子树和右子树。难点在于路径记录，path记录时如何保证当前父节点路径不变而只改变后加入的子节点路径。令每个结点进入搜索时当前val值加入到path，退出搜索回溯父节点前，再从path中退出来。

   public void dfs( List<List<Integer>> list,List<Integer> path,TreeNode root,int target)  //注意整形Integer首字母要大写
       {
           if(root.right==null&&root.left==null)//叶子节点
           {
           if(target==root.val)
           {
               path.add(target);
               list.add(new ArrayList<>(path));
               path.remove(path.size()-1);
               return;
           }
           }       
           path.add(root.val); //先进
           if(root.left!=null) //不用root判空
           dfs(list,path,root.left,target-root.val);
           if(root.right!=null)
           dfs(list,path,root.right,target-root.val);
           path.remove(path.size()-1);  //后退
       }
   }