검지offer24: 두 갈래 트리 중 어느 값의 경로
2103 단어 검지offer
제목 설명
두 갈래 나무의 루트 노드와 정수를 입력하고 사전 순서에 따라 두 갈래 나무의 결점 값과 정수를 입력하기 위한 모든 경로를 출력합니다.경로는 나무의 뿌리 결점에서 시작하여 잎 결점까지 내려가는 결점으로 경로를 형성합니다.
예제 1
입력
{10,5,12,4,7},22반환값
[[10,5,7],[10,12]]사고방식: 트레이스 경로를 가진 귀속 방법을 사용한다.두 개의 변수를 사용해야 한다. 하나의 변수는 귀속 경로를 거슬러 올라가는 데 사용되고, 하나의 변수는 조건을 만족시키는 모든 결과를 기록하는 데 사용된다.
1. 공유 목록의 팝과 append를 통해 실현한다.장점: 모든 귀속된 창고는 같은 목록을 사용하면 메모리 소모를 줄일 수 있다.
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# ，
def FindPath(self, root, expectNumber):
# write code here
res = []
path = []
def recur(root, tar):
if not root:return
path.append(root.val)
tar -= root.val
if (tar == 0) and not root.left and not root.right:
res.append(list(path))
recur(root.left, tar)
recur(root.right, tar)
path.pop()
recur(root, expectNumber)
return res2. 각 층에 하나의 추가 저장 장치를 추가하여 실현한다.장점이 없는 것 같고, 단점이 더 큰 것 같다. 특히 귀속층이 많을 때 메모리를 차지하는 것이 더 크다.
class Solution:
# ，
def FindPath(self, root, expectNumber):
if not root:
return []
result = []
path = [root.val]
self.sums = expectNumber
self.DFS(root,result,path)
return result
def DFS(self,root,result,path):
if root.left == None and root.right == None and sum(path) == self.sums:
result.append(path)
if root.left != None:
self.DFS(root.left,result,path+[root.left.val])
if root.right != None:
self.DFS(root.right,result,path+[root.right.val])# 제목은 우객망에서 유래:https://www.nowcoder.com/practice/b736e784e3e34731af99065031301bca?tpId=13&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
20200326 - 검지offer 면접문제 27: 두 갈래 나무의 거울이솔 위 안에 28문제의 답안이 있는데 어떻게 꼬치는지 모르겠다.간단해....
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
