剑指offer之二叉树中和为某一值的路径

题目描述

image.png

刚开始的时候没有认真审题,没有看到一定是要从根节点到叶子节点的,以为到路径的中间也可以,卡顿了很长时间

解决代码:

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<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        ArrayList<ArrayList<Integer>> arr = new ArrayList();
        if(root == null)    return arr;
        ArrayList<Integer> array = new ArrayList();
        
        int sum = 0;
        pa(root,target,arr,array,sum);
        return arr;
    }
    public void pa(TreeNode root,int target,ArrayList<ArrayList<Integer>> arr,
ArrayList<Integer> array,int sum){
        if(root == null)    return;
        sum += root.val;
        if(root.left == null && root.right == null){
            if(sum == target){
                array.add(root.val);
                arr.add(new ArrayList<Integer>(array));
                array.remove(array.size()-1);
            }
            return;
        }
        array.add(root.val);
        pa(root.left,target,arr,array,sum);
        pa(root.right,target,arr,array,sum);
        array.remove(array.size()-1);
    }
}

要注意array.remove(array.size()-1)这个操作,当目前的情况行不通,或者是左子树已经满足条件,需要进行判断右子树的时候,需要把最后一个元素去掉,这里使用递归的方法,每个方式共同操作同一个array,当需要进行添加到arr的时候,再新建一个ArrayList,不过使用new ArrayList(array);这种方法我还是第一次见,会有第二次的。

Copyright: 采用 知识共享署名4.0 国际许可协议进行许可

Links: https://hadoo666.top/archives/剑指offer之二叉树中和为某一值的路径