最新消息:XAMPP默认安装之后是很不安全的,我们只需要点击左方菜单的 "安全"选项,按照向导操作即可完成安全设置。

数组篇5_路径总和 II解题思路

XAMPP案例 admin 334浏览 0评论

来源:LeetCode

难度:中等

描述:

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

叶子节点 是指没有子节点的节点。

 

示例1:

drf00033

输入:root= [5,4,8,11,null,13,4,7,2,null,null,5,1],targetSum=22

输出:[[5,4,11,2],[5,8,4,5]]

示例2:

drf000033

分析:本题要求找出所有从根节点到叶子节点 路径总和等于给定目标和的路径,对于这类求所有可能性的题目,自然而然想到回溯法,由于给出的是一颗二叉树,咱们采用深度优先遍历的方式遍历二叉树,往下走一步,将targetSum减去本节点的值(也可采用节点值累加向下传递的方式),如下图

drf00033

题外话:对于求所有解,一般都能采用回溯法,使用回溯法时注意好choose、explore、un choose三步骤即可

 

解题

方法一:回溯法 + dfs解题

思路:对于二叉树深度优先遍历,先遍历左子树,再遍历右子树,先判断了当前节点的左子树或右子树不为空,再 choose 当前值,当满足条件时,将满足条件节点的值,加入到集合中,注意回退时要剪枝

代码:

 1public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
 2    List<List<Integer>> res = new ArrayList<>();
 3    if(null == root) return res;
 4    dfs(root, targetSum, res, new ArrayList<Integer>());
 5    return res;
 6}
 7
 8private void dfs(TreeNode root, int targetSum, 
 9                 List<List<Integer>> res, List<Integer> cur) {
10    // 左右子树均为空,说明当前节点是一个叶子节点
11    if (root.left == null && root.right == null) {
12        // 满足条件。注意,将最后一个元素加入到集合中
13        if (targetSum - root.val == 0) {
14            cur.add(root.val);
15            //add时创建新数组,防止一直沿用到一个数组
16            res.add(new ArrayList<>(cur));
17            //回溯 剪枝
18            cur.remove(cur.size() - 1);
19        }
20        return;
21    }
22    // 遍历左子树
23    if (root.left != null) {
24        // choose
25        cur.add(root.val);
26        // explore
27        dfs(root.left, targetSum - root.val, res, cur);
28        // un choose
29        cur.remove(cur.size() - 1);
30    }
31    // 遍历右子树
32    if (root.right != null) {
33        // choose
34        cur.add(root.val);
35        // explore
36        dfs(root.right, targetSum - root.val, res, cur);
37        // un choose
38        cur.remove(cur.size() - 1);
39    }
40}

代码写法优化,提前将本节点放入集合内:

 1public List<List<Integer>> pathSum(TreeNode root, int sum) {
 2    if (root == null) {
 3        return null;
 4    }
 5    List<List<Integer>> result = new ArrayList<>();
 6    pathSumList(root, sum, result, new ArrayList<>());
 7    return result;
 8}
 9
10private void pathSumList(TreeNode root, int sum,
11                         List<List<Integer>> result, List<Integer> cur) {
12    if (root == null) {
13        return;
14    }
15    //提前将本节点添加进数组
16    cur.add(root.val);
17    if (root.left == null && root.right == null) {
18        if (root.val == sum) {
19            //重新创建数组 防止一直使用一个数组
20            result.add(new ArrayList<>(cur));
21        }
22        //剪枝 去掉本节点
23        cur.remove(cur.size() - 1);
24        return;
25    }
26    //左子树
27    pathSumList(root.left, sum - root.val, result, cur);
28    //右子树
29    pathSumList(root.right, sum - root.val, result, cur);
30    //剪枝 去掉本节点
31    cur.remove(cur.size() - 1);
32}

方法二:广度优先遍历解题

思路:通过广度优先遍历二叉树,采用两个队列分别存储当前节点以及到达当前节点的路径节点值,当 当前节点为叶子节点且值和目的值一致时,将该条路径放入结果集当中

代码:

 1public List<List<Integer>> pathSum(TreeNode root, int sum) {
 2    List<List<Integer>> res = new ArrayList<>();
 3    //如果节点为空直接返回
 4    if (root == null) {
 5        return res;
 6    }
 7    //使用两个队列,一个存储结点,一个存储从更结点到当前节点的路径
 8    Queue<TreeNode> queueNode = new LinkedList<>();
 9    Queue<List<Integer>> queueList = new LinkedList<>();
10    //根节点入队
11    queueNode.add(root);
12    //根节点的路径入队
13    List<Integer> list = new ArrayList<>();
14    list.add(root.val);
15    queueList.add(list);
16    while (!queueNode.isEmpty()) {
17        //当前节点出队
18        TreeNode node = queueNode.poll();
19        //当前节点的路径出队
20        List<Integer> tempList = queueList.poll();
21        if (node.left == null && node.right == null && node.val == sum) {
22            //如果满足条件,就把路径存储到res中
23            res.add(tempList);
24        }
25        //左子节点不为空,左子节点和路径入队
26        if (node.left != null) {
27            tempList.add(node.left.val);
28            queueList.add(new ArrayList<>(tempList));
29            //将本节点值累加到其左右节点上去
30            node.left.val += node.val;
31            queueNode.add(node.left);
32            //由于还有右节点,且左节点已加入到List当中,故需剔除该左节点值
33            tempList.remove(tempList.size() - 1);
34        }
35        //右子节点不为空,右子节点和路径入队
36        if (node.right != null) {
37            tempList.add(node.right.val);
38            queueList.add(new ArrayList<>(tempList));
39            //将本节点值累加到其左右节点上去
40            node.right.val += node.val;
41            queueNode.add(node.right);
42        }
43    }
44    return res;
45}

以上仅是个人思路解法

转载请注明:XAMPP中文组官网 » 数组篇5_路径总和 II解题思路

您必须 登录 才能发表评论!