关注Java领域相关技术 记录有趣的事情

LeetCode-113. 路径总和 II

US-B.Ralph
US-B.Ralph
2020-09-26

问题地址

LeetCode每日一题/2020-09-26

LeetCode113. 路径总和 II

问题描述

规则

  • 给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

说明:

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

注意

  • 你可以假设树中没有重复的元素。

示例

  • 示例一：
给定如下二叉树，以及目标和 sum = 22，

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1
返回:
[
   [5,4,11,2],
   [5,8,4,5]
]

解析

解题思路

  • 从根节点开始遍历每一条路径，当遍历到叶子节点且该路径节点之和等于sum则将其添加到结果集中；

数据操作分析

  • 遍历整棵树
    • 当节点为空，直接返回；
    • 否则sum=sum-node.val，并将该节点添加到路径中；
    • 当到达叶子节点且sum=0，将该路径添加到结果集中；
    • 如果没有到达叶子节点，则继续遍历左子树和右子树；
    • 最后的值用完之后还没有添加到结果集中说明该值不符合条件，需要做移出处理；

复杂度分析

  1. 时间复杂度
  2. 空间复杂度

编码实现

public class LeetCode0113_PathSumii {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> tem = new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        int inx = 0;
        dfs(root, sum, inx);
        return ans;
    }
    private void dfs(TreeNode root, int sum) {
        if (root == null) return;
        sum -= root.val;
        tem.add(root.val);
        if (root.left == null && root.right == null && sum == 0) {
            ans.add(new ArrayList<>(tem));
        }
        dfs(root.left, sum);
        dfs(root.right, sum);
        tem.remove(tem.size() - 1);
    }
}

官方解法

注意到本题的要求是，找到所有满足从「根节点」到某个「叶子节点」经过的路径上的节点之和等于目标和的路径。核心思想是对树进行一次遍历，在遍历时记录从根节点到当前节点的路径和，以防止重复计算。

方法一：深度优先搜索

思路：

  • 我们可以采用深度优先搜索的方式，枚举每一条从根节点到叶子节点的路径。当我们遍历到叶子节点，且此时路径和恰为目标和时，我们就找到了一条满足条件的路径。

复杂度分析：

  1. 时间复杂度:O(N^2)，其中 N 是树的节点数。在最坏情况下，树的上半部分为链状，下半部分为完全二叉树，并且从根节点到每一个叶子节点的路径都符合题目要求。此时，路径的数目为 O(N)，并且每一条路径的节点个数也为 O(N)，因此要将这些路径全部添加进答案中，时间复杂度为 O(N^2)。

  2. 空间复杂度：O(N)，其中 N 是树的节点数。空间复杂度主要取决于栈空间的开销，栈中的元素个数不会超过树的节点数。

编码实现

class Solution {
    List<List<Integer>> ret = new LinkedList<List<Integer>>();
    Deque<Integer> path = new LinkedList<Integer>();

    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        dfs(root, sum);
        return ret;
    }

    public void dfs(TreeNode root, int sum) {
        if (root == null) {
            return;
        }
        path.offerLast(root.val);
        sum -= root.val;
        if (root.left == null && root.right == null && sum == 0) {
            ret.add(new LinkedList<Integer>(path));
        }
        dfs(root.left, sum);
        dfs(root.right, sum);
        path.pollLast();
    }
}

方法一：广度优先搜索

思路及算法：

  • 我们也可以采用广度优先搜索的方式，遍历这棵树。当我们遍历到叶子节点，且此时路径和恰为目标和时，我们就找到了一条满足条件的路径。
  • 为了节省空间，我们使用哈希表记录树中的每一个节点的父节点。每次找到一个满足条件的节点，我们就从该节点出发不断向父节点迭代，即可还原出从根节点到当前节点的路径。

复杂度分析：

  1. 时间复杂度:O(N^2)，其中 N 是树的节点数。分析思路与方法一相同。

  2. 空间复杂度：O(N)，其中 N 是树的节点数。空间复杂度主要取决于哈希表和队列空间的开销，哈希表需要存储除根节点外的每个节点的父节点，队列中的元素个数不会超过树的节点数。

编码实现

class Solution {
    List<List<Integer>> ret = new LinkedList<List<Integer>>();
    Map<TreeNode, TreeNode> map = new HashMap<TreeNode, TreeNode>();

    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        if (root == null) {
            return ret;
        }

        Queue<TreeNode> queueNode = new LinkedList<TreeNode>();
        Queue<Integer> queueSum = new LinkedList<Integer>();
        queueNode.offer(root);
        queueSum.offer(0);

        while (!queueNode.isEmpty()) {
            TreeNode node = queueNode.poll();
            int rec = queueSum.poll() + node.val;

            if (node.left == null && node.right == null) {
                if (rec == sum) {
                    getPath(node);
                }
            } else {
                if (node.left != null) {
                    map.put(node.left, node);
                    queueNode.offer(node.left);
                    queueSum.offer(rec);
                }
                if (node.right != null) {
                    map.put(node.right, node);
                    queueNode.offer(node.right);
                    queueSum.offer(rec);
                }
            }
        }

        return ret;
    }

    public void getPath(TreeNode node) {
        List<Integer> temp = new LinkedList<Integer>();
        while (node != null) {
            temp.add(node.val);
            node = map.get(node);
        }
        Collections.reverse(temp);
        ret.add(new LinkedList<Integer>(temp));
    }
}

精彩评论

跳转地址1：DFS，BFS共5种方式解决，2种击败了100%的用户

递归

思路：
  • 这题没说sum是正数还是负数，也没说树中节点的值有没有负数。我们要做的是从根节点到叶子节点遍历他所有的路径，返回他所有路径中和等于sum的节点，这里有两种实现方式，一种是减，一种是加。减就是从根节点开始，用sum不断的减去遍历到的每一个节点，一直到叶子节点，在减去叶子节点之前查看sum是否等于叶子节点，如果等于说明我们找到了一组，画个图看一下
编码实现
public List<List<Integer>> pathSum(TreeNode root, int sum) {
    List<List<Integer>> result = new ArrayList<>();
    dfs(root, sum, new ArrayList<>(), result);
    return result;
}

public void dfs(TreeNode root, int sum, List<Integer> list,
                List<List<Integer>> result) {
    //如果节点为空直接返回
    if (root == null)
        return;
    //因为list是引用传递，为了防止递归的时候分支污染，我们要在每个路径
    //中都要新建一个subList
    List<Integer> subList = new ArrayList<>(list);
    //把当前节点值加入到subList中
    subList.add(new Integer(root.val));
    //如果到达叶子节点，就不能往下走了，直接return
    if (root.left == null && root.right == null) {
        //如果到达叶子节点，并且sum等于叶子节点的值，说明我们找到了一组，
        //要把它放到result中
        if (sum == root.val)
            result.add(subList);
        //到叶子节点之后直接返回，因为在往下就走不动了
        return;
    }
    //如果没到达叶子节点，就继续从他的左右两个子节点往下找，注意到
    //下一步的时候，sum值要减去当前节点的值
    dfs(root.left, sum - root.val, subList, result);
    dfs(root.right, sum - root.val, subList, result);
}

回溯，往下减

思路：
  • 上面只是对二叉树的深度优先搜索（DFS），并没有使用回溯，之前讲递归的时候提到过为了防止分支污染我们还可以把使用过的值在返回的时候把它给remove掉，这就是大家常提的回溯算法，也可以看下之前讲的426，什么是递归，通过这篇文章，让你彻底搞懂递归，看下代码:
编码实现
public List<List<Integer>> pathSum(TreeNode root, int sum) {
    List<List<Integer>> result = new ArrayList<>();
    dfs(root, sum, new ArrayList<>(), result);
    return result;
}

public void dfs(TreeNode root, int sum, List<Integer> list,
                List<List<Integer>> result) {
    //如果节点为空直接返回
    if (root == null)
        return;
    //把当前节点值加入到list中
    list.add(new Integer(root.val));
    //如果到达叶子节点，就不能往下走了，直接return
    if (root.left == null && root.right == null) {
        //如果到达叶子节点，并且sum等于叶子节点的值，说明我们找到了一组，
        //要把它放到result中
        if (sum == root.val)
            result.add(new ArrayList(list));
        //注意别忘了把最后加入的结点值给移除掉，因为下一步直接return了，
        //不会再走最后一行的remove了，所以这里在rerurn之前提前把最后
        //一个结点的值给remove掉。
        list.remove(list.size() - 1);
        //到叶子节点之后直接返回，因为在往下就走不动了
        return;
    }
    //如果没到达叶子节点，就继续从他的左右两个子节点往下找，注意到
    //下一步的时候，sum值要减去当前节点的值
    dfs(root.left, sum - root.val, list, result);
    dfs(root.right, sum - root.val, list, result);
    //我们要理解递归的本质，当递归往下传递的时候他最后还是会往回走，
    //我们把这个值使用完之后还要把它给移除，这就是回溯
    list.remove(list.size() - 1);
}

回溯，往下累加

思路：
  • 上面是减的方式，我们再来看一个加的方式，其实他就是从根节点开始到叶子节点把这个路径上的所有节点都加起来，最后查看是否等于sum，画个图看一下
编码实现
public List<List<Integer>> pathSum(TreeNode root, int sum) {
    List<List<Integer>> result = new ArrayList<>();
    dfs(root, sum, 0, new ArrayList<>(), result);
    return result;
}
public void dfs(TreeNode root, int sum, int toal, List<Integer> list,
                List<List<Integer>> result) {
    //如果节点为空直接返回
    if (root == null)
        return;
    //把当前节点值加入到list中
    list.add(new Integer(root.val));
    //没往下走一步就要计算走过的路径和
    toal += root.val;
    //如果到达叶子节点，就不能往下走了，直接return
    if (root.left == null && root.right == null) {
        //如果到达叶子节点，并且sum等于toal，说明我们找到了一组，
        //要把它放到result中
        if (sum == toal)
            result.add(new ArrayList(list));
        //注意别忘了把最后加入的结点值给移除掉，因为下一步直接return了，
        //不会再走最后一行的remove了，所以这里在rerurn之前提前把最后
        //一个结点的值给remove掉。
        list.remove(list.size() - 1);
        //到叶子节点之后直接返回，因为在往下就走不动了
        return;
    }
    //如果没到达叶子节点，就继续从他的左右两个子节点往下找
    dfs(root.left, sum, toal, list, result);
    dfs(root.right, sum, toal, list, result);
    //我们要理解递归的本质，当递归往下传递的时候他最后还是会往回走，
    //我们把这个值使用完之后还要把它给移除，这就是回溯
    list.remove(list.size() - 1);
}

BFS解决

思路：
  • 上面几种方式无论加还是减，都是二叉树的DFS，这里还可以使用二叉树的BFS解决，就是一行一行的遍历
编码实现
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> res = new ArrayList<>();
        //如果节点为空直接返回
        if (root == null)
            return res;
        //使用两个队列，一个存储结点，一个存储从更结点到当前节点的路径
        Queue<TreeNode> queueNode = new LinkedList<>();
        Queue<List<Integer>> queueList = new LinkedList<>();
        //根节点入队
        queueNode.add(root);
        //根节点的路径入队
        List<Integer> list = new ArrayList<>();
        list.add(root.val);
        queueList.add(list);

        while (!queueNode.isEmpty()) {
            //当前节点出队
            TreeNode node = queueNode.poll();
            //当前节点的路径出队
            List<Integer> tempList = queueList.poll();
            if (node.left == null && node.right == null && node.val == sum) {
                //如果满足条件，就把路径存储到res中
                res.add(tempList);
            }
            //左子节点不为空，左子节点和路径入队
            if (node.left != null) {
                tempList.add(node.left.val);
                queueList.add(new ArrayList<>(tempList));
                node.left.val += node.val;
                queueNode.add(node.left);
                tempList.remove(tempList.size() - 1);
            }
            //右子节点不为空，右子节点和路径入队
            if (node.right != null) {
                tempList.add(node.right.val);
                queueList.add(new ArrayList<>(tempList));
                node.right.val += node.val;
                queueNode.add(node.right);
            }
        }
        return res;
    }

深度优先搜索非递归解决

思路：
  • 树的dfs递归代码比较简单，我们来看一下树的dfs非递归的写法
    public void treeDFS(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        stack.add(root);
        while (!stack.empty()) {
            TreeNode node = stack.pop();
            System.out.println(node.val);
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
    }
  • 可以参照上面的代码进行修改，代码和第4种方式相似度比较高，不同的是第4种方式使用的是队列，而这里使用的是栈
编码实现
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> res = new ArrayList<>();
        //如果节点为空直接返回
        if (root == null)
            return res;
        Stack<TreeNode> stackNode = new Stack<>();
        Stack<List<Integer>> stackList = new Stack<>();
        stackNode.add(root);

        List<Integer> list = new ArrayList<>();
        list.add(root.val);
        stackList.add(list);
        while (!stackNode.empty()) {
            TreeNode node = stackNode.pop();
            List<Integer> tempList = stackList.pop();
            if (node.left == null && node.right == null && node.val == sum) {
                //如果满足条件，就把路径存储到res中
                res.add(tempList);
            }

            if (node.right != null) {
                tempList.add(node.right.val);
                stackList.add(new ArrayList<>(tempList));
                node.right.val += node.val;
                stackNode.push(node.right);
                tempList.remove(tempList.size() - 1);

            }
            if (node.left != null) {
                tempList.add(node.left.val);
                stackList.add(new ArrayList<>(tempList));
                node.left.val += node.val;
                stackNode.push(node.left);
                tempList.remove(tempList.size() - 1);
            }
        }
        return res;
    }
US-B.Ralph
LeetCode数据结构与算法算法

Leave a Comment

邮箱地址不会被公开。 必填项已用*标注

7 + 12 =