LeetCode-python 112.경로 합계

1833 단어
제목 링크 난이도: 단순 유형: 두 갈래 트리, 깊이 우선 검색, 귀속
두 갈래 나무와 목표를 정하고 이 나무에 뿌리 노드가 잎 노드까지의 경로가 있는지 판단한다. 이 경로에 있는 모든 노드 값은 목표와 같다.
설명: 잎 노드는 하위 노드가 없는 노드를 가리킨다.
예는 다음과 같은 두 갈래 트리와 목표와sum=22를 지정합니다
              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

문제 풀이 사고방식


깊이 우선 검색, 잎 노드를 검색할 때만 총계가 목표와 같은지 판단하고, 경로 총계가 목표와 같으면true로 되돌아갑니다
잎 노드가 아니라면 이 노드의 아이 노드를 각각 깊이 우선 검색합니다

코드 구현


깊이 우선 순위 검색
# 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):
    def hasPathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: bool
        """
        res = []
        def dfs(target, root):
            if not root.left and not root.right:
                if root.val == target:
                    res.append(True)
            if root.left:
                dfs(target-root.val, root.left)
            if root.right:
                dfs(target-root.val, root.right)
        if not root:
            return False
        dfs(sum, root)
        return any(res)

귀속:
class Solution(object):
    def hasPathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: bool
        """
        if not root:
            return False
        if not root.left and not root.right and sum = root.val:
            return True
        sum -= root.val
        return self.hasPathSum(root.left, sum) or self.hasPathSum(root.right, sum)

본문 링크:https://www.jianshu.com/p/6f15488d42aa

좋은 웹페이지 즐겨찾기