leetcode [113]Path Sum II

发布时间：2020-12-14 04:33:39 所属栏目：大数据来源：网络整理

导读：Given a binary tree and a sum,find all root-to-leaf paths where each path‘s sum equals the given sum. Note:?A leaf is a node with no children. Example: Given the below binary tree and? sum = 22 , 5 / 4 8 / / 11 13 4 / / 7 2 5 1 Return:

Given a binary tree and a sum,find all root-to-leaf paths where each path‘s sum equals the given sum.

Note:?A leaf is a node with no children.

Example:

Given the below binary tree and?sum = 22,

      5
     /     4   8
   /   /   11  13  4
 /      / 7    2  5   1

Return:

[
   [5,4,11,2],[5,8,5]
]

题目大意：

找出从根节点到叶子节点路径上和为给定sum的路径。

解法：

先开始是用dfs做的，后来发现自己的dfs会将一个路径添加两次。因为在递归到叶子节点的左右都是为空的，这时就会在res数组中添加两次。

java:

class Solution {
    private void dfs(List<List<Integer>>res,List<Integer>tmp,TreeNode node,int tmpSum){
        if(node==null){
            if(tmpSum==0) {
                res.add(new ArrayList<>(tmp));
            }
            return;
        }
        if(tmpSum<0) return;
        tmp.add(node.val);
        dfs(res,tmp,node.left,tmpSum-node.val);
        dfs(res,node.right,tmpSum-node.val);
        tmp.remove(tmp.size()-1);
    }

    public List<List<Integer>> pathSum(TreeNode root,int sum) {
        List<List<Integer>>res=new ArrayList<>();
        List<Integer>tmp=new ArrayList<>();
        dfs(res,root,sum);
        return res;
    }
}

改了之后递归结束的条件就是节点的左右子节点都为空，则当前节点就是叶子节点。　

java:

class Solution {
    private void dfs(List<List<Integer>>res,int tmpSum){
        if(node.left==null&&node.right==null){
            if(tmpSum==0) {
                res.add(new ArrayList<>(tmp));
            }
            return;
        }
        if(node.left!=null) {
            tmp.add(node.left.val);
            dfs(res,tmpSum - node.left.val);
            tmp.remove(tmp.size() - 1);
        }
        if(node.right!=null) {
            tmp.add(node.right.val);
            dfs(res,tmpSum - node.right.val);
            tmp.remove(tmp.size() - 1);
        }
    }

    public List<List<Integer>> pathSum(TreeNode root,int sum) {
        List<List<Integer>>res=new ArrayList<>();
        if(root==null) return res;
        List<Integer>tmp=new ArrayList<>();
        tmp.add(root.val);
        dfs(res,sum-root.val);
        return res;
    }
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!