[LeetCode] 113. Path Sum II Java

╰+攻爆jí腚メ 2021-10-01 00:48 226阅读 0赞

**题目：**

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

For 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,4,5]
    ]

** 题意及分析：**输出从根节点到叶子节点的路径上所有点之和==sum的路径。遍历树，遍历到每个非叶子节点，减去该点的值，并加入路径中(list)，到达叶子节点时，判断，如果sum-node.val==0那么将该点添加到路径，并添加到结果中，否则继续遍历。对每个点，用一个list保存，根节点到当前点的路径。

**代码：**

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public List<List<Integer>> pathSum(TreeNode root, int sum) {
            List<List<Integer>> res = new ArrayList<>();
            if(root==null) return res;
            List<Integer> list = new ArrayList<>();
            getPath(res,list,root,sum);
            return res;
        }
    
        public void getPath( List<List<Integer>> res,List<Integer> list,TreeNode node,int sum){
            List<Integer> newList = new ArrayList<>(list);
            if(node.left==null&&node.right==null){ //遍历到根节点
                if(sum-node.val==0) {   //满足条件
                    newList.add(node.val);
                    res.add(new ArrayList<>(newList));
                    newList.clear();
                }
                return;
            }
            newList.add(node.val);
            if(node.left!=null){
                getPath(res,newList,node.left,sum-node.val);
            }
            if(node.right!=null){
                getPath(res,newList,node.right,sum-node.val);
            }
        }
    
    }

** **

--------------------

Seen this qu

转载于:https://www.cnblogs.com/271934Liao/p/7216388.html