1. 首页

LeetCode 113. 路径总和 II

题目描述

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

说明: 叶子节点是指没有子节点的节点。

示例:
给定如下二叉树,以及目标和 sum = 22,

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

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

难度:Middle

前置知识

  • 回溯法

公司

  • 阿里
  • 腾讯
  • 百度
  • 字节

思路

这道题目是求集合,并不是求值,而是枚举所有可能,因此动态规划不是特别切合,因此我们需要考虑别的方法。

这种题目其实有一个通用的解法,就是回溯法。网上也有大神给出了这种回溯法解题的通用写法,这里的所有的解法使用通用方法解答。
除了这道题目还有很多其他题目可以用这种通用解法,具体的题目见后方相关题目部分。

我们先来看下通用解法的解题思路,我画了一张图:

LeetCode 113. 路径总和 II

图是 78.subsets,都差不多,仅做参考。

通用写法的具体代码见下方代码区。

关键点解析

  • 回溯法
  • backtrack 解题公式

代码

  • 语言支持:JS,C++,Python3

JavaScript Code:

/*
 * @lc app=leetcode id=113 lang=javascript
 *
 * [113] Path Sum II
 */
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
function backtrack(root, sum, res, tempList) {
  if (root === null) return;
  if (root.left === null && root.right === null && sum === root.val)
    return res.push([...tempList, root.val]);

  tempList.push(root.val);
  backtrack(root.left, sum - root.val, res, tempList);

  backtrack(root.right, sum - root.val, res, tempList);
  tempList.pop();
}
/**
 * @param {TreeNode} root
 * @param {number} sum
 * @return {number[][]}
 */
var pathSum = function (root, sum) {
  if (root === null) return [];
  const res = [];
  backtrack(root, sum, res, []);
  return res;
};

C++ Code:

/**
 * @来源: Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * @介绍:是以前端进阶资源教程分享为主的专业网站,包括:前端、大厂面试题、typescript教程、程序人生、React.js
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        auto ret = vector<vector<int>>();
        auto temp = vector<int>();
        backtrack(root, sum, ret, temp);
        return ret;
    }
private:
    void backtrack(const TreeNode* root, int sum, vector<vector<int>>& ret, vector<int>& tempList) {
        if (root == nullptr) return;
        tempList.push_back(root->val);
        if (root->val == sum && root->left == nullptr && root->right == nullptr) {
            ret.push_back(tempList);
        } else {
            backtrack(root->left, sum - root->val, ret, tempList);
            backtrack(root->right, sum - root->val, ret, tempList);
        }
        tempList.pop_back();
    }
};
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
        if not root:
            return []

        result = []

        def trace_node(pre_list, left_sum, node):
            new_list = pre_list.copy()
            new_list.append(node.val)
            if not node.left and not node.right:
                # 这个判断可以和上面的合并,但分开写会快几毫秒,可以省去一些不必要的判断
                if left_sum == node.val:
                    result.append(new_list)
            else:
                if node.left:
                    trace_node(new_list, left_sum-node.val, node.left)
                if node.right:
                    trace_node(new_list, left_sum-node.val, node.right)

        trace_node([], sum, root)
        return result

相关题目

看完两件小事

如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:

  1. 关注我们的 GitHub 博客,让我们成为长期关系
  2. 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
  3. 关注公众号 「画漫画的程序员」,公众号后台回复「资源」 免费领取我精心整理的前端进阶资源教程

JS中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。欢迎热爱技术的你一起加入交流与学习,JS中文网的使命是帮助开发者用代码改变世界

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Js中文网 · 前端进阶资源教程 」https://www.javascriptc.com

标题:LeetCode 113. 路径总和 II

链接:https://www.javascriptc.com/4476.html

« LeetCode 114. 二叉树展开为链表
LeetCode 112. 路径总和»
Flutter 中文教程资源

相关推荐

QR code