每天分享一个LeetCode题目

每天 5 分钟，一起进步

LeetCode112 路径总和，地址: https://leetcode-cn.com/problems/path-sum/

这道题目是 LeetCode 中「树」路径总和的第一个题目，就是给定 targetSum ，去判断，自顶而下到叶子结点，整个路径有没有路径和为 targetSum 的路径，有就返回 True，否则，返回 False。

树结点定义

class TreeNode(object):
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

递归方式

依然递归方式比较简单，就是一个先续遍历，先判断当前结点是否有孩子结点

如果有，则继续向下判断

如果没有，则该结点是叶子结点，判断是否满足给定目标值 targetSum 的条件。

具体思路是，在不断的先序递归遍历中，每次递归，都要用 targetSum 减去当前结点值，当到了叶子结点的时候，判断被不断减掉的 targetSum 当前的值是否和单当前结点值相同。若相同，返回 True。

def hasPathSum(self, root, targetSum):
    if not root:
        return False
    if not root.left and not root.right and targetSum == root.val:
        return True
    return self.hasPathSum(root.left, targetSum-root.val) or self.hasPathSum(root.right, targetSum-root.val)

这就是一个简单的先序遍历，对于递归思维方式解决有关「树」的题目的时候，还是比较不容易想清楚.

多思考，多练习。

非递归方式

使用层序遍历的思考过程。

在不断遍历访问结点的过程中，需要记录两个值，一个是结点，另外一个是从根结点到当前结点路径和，这里我们用 Python 的元祖来表示(结点, 从根结点到当前结点路径和)

层序遍历的过程，这里先不赘述了，需要看详细说明的，可以转战这里https://mp.weixin.qq.com/s/nTB41DvE7bfrT7_rW_gfXw，有详细的图表说明。

看代码：

def hasPathSum_bfs(self, root, targetSum):
    if not root:
        return False
    queue = collections.deque()
    # 使用元祖存放结点信息(结点,当前结点自顶向下路径和)
    queue.append((root, root.val))
    while queue:
        node, node_val = queue.pop()
        if not node.left and not node.right and node_val == targetSum:
            return True
        if node.left:
            queue.appendleft((node.left, node.left.val + node_val))
        if node.right:
            queue.appendleft((node.right, node.right.val + node_val))
    return False

尤其是很多地方都会使用像这种 BFS 的方式进行遍历访问，而且主要适用于一些从顶向下的题目。这个是一道很典型的从顶向下题目。

对于这一类从顶向下的题目，使用 BFS 的思路是非常清晰的。

全部代码

# -*- coding:utf-8 -*-
# !/usr/bin/env python

import collections

# 树结点类
class TreeNode(object):
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution(object):
    def hasPathSum(self, root, targetSum):
        if not root:
            return False
        if not root.left and not root.right and targetSum == root.val:
            return True
        return self.hasPathSum(root.left, targetSum-root.val) or self.hasPathSum(root.right, targetSum-root.val)

    def hasPathSum_bfs(self, root, targetSum):
        if not root:
            return False
        queue = collections.deque()
        # 使用元祖存放结点信息(结点,当前结点自顶向下路径和)
        queue.append((root, root.val))
        while queue:
            node, node_val = queue.pop()
            if not node.left and not node.right and node_val == targetSum:
                return True
            if node.left:
                queue.appendleft((node.left, node.left.val + node_val))
            if node.right:
                queue.appendleft((node.right, node.right.val + node_val))
        return False


if __name__ == "__main__":
    # 新建节点
    root = TreeNode(5)
    node_B = TreeNode(3)
    node_C = TreeNode(6)
    node_D = TreeNode(1)
    node_E = TreeNode(2)
    node_F = TreeNode(4)
    node_G = TreeNode(9)
    node_H = TreeNode(7)
    node_I = TreeNode(0)
    node_J = TreeNode(9)
    # 构建二叉树
    #        5
    #      /       #     3     6
    #    / \   /     #   1   2 4   9
    #  /     # 7   0
    #          #       9
    root.left, root.right = node_B, node_C
    node_B.left, node_B.right = node_D, node_E
    node_C.left, node_C.right = node_F, node_G
    node_D.left, node_D.right = node_H, node_I
    node_I.right = node_J

    s = Solution()
    print(s.hasPathSum(root, 18))
    print(s.hasPathSum_bfs(root, 18))

Github

https://github.com/xiaozhutec/PyCode

玩的开心呀 ?( ′???` )

LeetCode112 | 路径总和