lintcode:二叉树的路径和

题目

给定一个二叉树，找出所有路径中各节点相加总和等于给定 目标值 的路径。

一个有效的路径，指的是从根节点到叶节点的路径。

解题

下面有个小bug

最后比较的时候是叶子节点为空，左右都有叶子结点，所有会出现重复的情况，聪明的你可能会想到保留不重复的结果

但是但一个树的结点都相同时候就不可以了

两层，三个结点，每个节点都是1，路径和是2

这样就有两个个答案[1,1]、[1,1]

所以再是叶子结点时候就要进行判断，这里的叶子结点要是真叶子节点，左右节点为空而自己不空

public class Solution {

    /**

     * @param root the root of binary tree

     * @param target an integer

     * @return all valid paths

     */

    public List<ArrayList<Integer>> binaryTreePathSum(TreeNode root, int target) {

        // Write your code here

        ArrayList<Integer> list = new ArrayList<Integer>();

        List<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();

        PathSum(root,target,result,list);

        return result;

    }

    public void PathSum(TreeNode root,int target,List<ArrayList<Integer>> result,ArrayList<Integer> list){

        if(target ==0 && root==null){

            ArrayList<Integer> l = new ArrayList<Integer>(list);

            if(!result.contains(l))

                result.add(l);

            return;

        }

        if( root==null)

            return;

        int val = root.val;

        list.add(val);

        ArrayList<Integer> list2 = new ArrayList<Integer>(list); 
　　　　

        PathSum(root.left,target-val,result,list);

　　　　 list.remove(list.size()-1);

        PathSum(root.right,target-val,result,list2);

        list2.remove(list2.size()-1);

    }

}

AC代码

public class Solution {

    /**

     * @param root the root of binary tree

     * @param target an integer

     * @return all valid paths

     */

    public List<ArrayList<Integer>> binaryTreePathSum(TreeNode root, int target) {

        // Write your code here

        ArrayList<Integer> list = new ArrayList<Integer>();

        List<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();

        PathSum(root,target,result,list);

        return result;

    }

    public void PathSum(TreeNode root,int target,List<ArrayList<Integer>> result,ArrayList<Integer> list){

        if( root==null)

            return;

        if( (target ==root.val) && root.left==null && root.right==null){

            list.add(root.val);

            ArrayList<Integer> l = new ArrayList<Integer>(list);

            // if(!result.contains(l))

                result.add(l);

            return;

        }

        int val = root.val;

        list.add(val);

        ArrayList<Integer> list2 = new ArrayList<Integer>(list);

        PathSum(root.left,target-val,result,list);

        list.remove(list.size()-1);

        PathSum(root.right,target-val,result,list2);

        list2.remove(list2.size()-1);

    }

}

巴特西

lintcode:二叉树的路径和

最新文章

热门文章