[Leet Code 매일 한 문제] 2020.7.07, 112.경로 합계
112. 경로 합계(단순)
두 갈래 나무와 목표를 정하고 이 나무에 뿌리 노드가 잎 노드까지의 경로가 있는지 판단한다. 이 경로에 있는 모든 노드 값은 목표와 같다.
설명: 잎 노드는 하위 노드가 없는 노드를 가리킨다.
예:
다음 두 갈래 나무와 목표와sum=22,
**5**
/ \
**4** 8
/ / \
**11** 13 4
/ \ \
7 **2** 1
분석:
두 갈래 나무의 구조는 귀착에 매우 적합하다. 우리는 뿌리 결점부터 잎 결점까지 잎 결점이 요구를 충족시켜야 정답이다.경로를 따라 아래로 내려갈 때 경로를 상태로 옮겨야 하기 때문에 귀속 함수 모델이 있습니다.
def checkSum(root TreeNode, cur int) -> bool:
return checkSum(root.left, cur + root.val) or checkSum(root.right, cur + root.val)
계속 점프 조건을 고려하여 현재 결점이 잎결점일 때 귀속은 반드시 멈춰야 하며, 현재 결점이 비어 있을 때 귀속도 계속할 수 없다.가입:
if not root:
return None
if not root.left and not root.right:
if cur + root.Val == sum:
return True
코드(Golang):
func hasPathSum(root *TreeNode, sum int) bool {
var checkSum func(root *TreeNode, sum int) bool
checkSum = func(root *TreeNode, cur int) bool {
if root == nil {
return false
}
if root.Val + cur == sum && root.Left == nil && root.Right == nil {
return true
}
return checkSum(root.Left, cur + root.Val) || checkSum(root.Right, cur + root.Val)
}
return checkSum(root, 0)
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
