【leetcode刷题】T135-路径总和 III

木又AI帮

发布于 2019-08-08 16:13:41

3790

发布于 2019-08-08 16:13:41

文章被收录于专栏：木又AI帮

木又连续日更第91天（91/100）

木又的第135篇leetcode解题报告

二叉树类型第25篇解题报告

leetcode第437题：路径总和 III

https://leetcode-cn.com/problems/path-sum-iii/

【题目】

给定一个二叉树，它的每个结点都存放着一个整数值。

找出路径和等于给定数值的路径总数。

路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。

示例：
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1
返回 3。和等于 8 的路径有:
1.  5 -> 3
2.  5 -> 2 -> 1
3.  -3 -> 11

【思路】

这道题，我只想出最笨的解法。

递归遍历，遍历孩子节点时，有两种情况：一是将孩子节点当做根节点，查找路径，sum变为最原始的值；二是孩子节点只是路径中的一个点，sum变为sum - node->val。当sum == node->val时，结果res++。

需要注意的是，每个节点当做根节点（即sum变为最原始的值），再进行递归遍历，只能一次，需要判断。

看网上解答，可以采用hash表，dfs等方法，我们一起思考吧。

【代码】

python版本

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    d = {}
    def pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: int
        """
        self.org_sum = sum
        return self.count(root, True, sum)

    def count(self, node, restart, sum):
        if restart:
            if node in self.d:
                return 0
            else:
                self.d[node] = 1
        if not node:
            return 0
        res = 0
        if sum == node.val:
            res += 1
        return res + self.count(node.left, False, sum - node.val) + self.count(node.right, False, sum - node.val) + self.count(node.left, True, self.org_sum) + self.count(node.right, True, self.org_sum)

C++版本

/**
 * 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 {
    int org_sum = 0;
    map<TreeNode*, int> d;
public:
    int pathSum(TreeNode* root, int sum) {
        org_sum = sum;
        return get_count(root, true, sum);
    }

    int get_count(TreeNode* node, bool restart, int sum){
        if(!node)
            return 0;
        if(restart){
            if(d.find(node) == d.end())
                d[node] = 1;
            else
                return 0;
        }
        int res = 0;
        if(sum == node->val)
            res++;
        return res + get_count(node->left, false, sum-node->val) + get_count(node->right, false, sum-node->val) + get_count(node->left, true, org_sum) + get_count(node->right, true, org_sum);
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2019-08-06，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树