재귀

Question

내가 같은 이진 트리가 있다고 가정 :

내가이 경우 (5+3+2+6)/(4) = 4있는 나무의 평균 값을 반환하는 함수를 만들려고합니다.

나는 여기에 내 기능을 통과를 예약 주문 및 수행

def helper(root, total=0, amount=0): 
    if root != None: 
     total += root.data 
     amount += 1 
     helper(root.left, total, amount) 
     helper(root.right, total, amount)  

    return (root, total, amount) 

def avg(root): 
    av = helper(root) 
    return av[1]/av[2] 

그러나이 코드는 (Node 5, total = 5, amount = 1)를 반환합니다. 그것은 단지 first 노드를 스캔하는 것과 같고 위의 코드가 왜 또는 무엇이 잘못되었는지를 알지 못합니다.

class btn(object): 

    def __init__(self, data): 
     self.data = data 
     self.left = None 
     self.right = None 

Answer 1

안티 패턴은 이미 상태 변수와 재귀를 사용하고

를 발견했습니다.이 페이지의 다른 답변은 같은 실수

def avg (tree): 
    def helper (node, sum, count): 
    if node is None: 
     return (0, 0) 
    else: 
     (Lsum, Lcount) = helper(node.left, 0, 0) 
     (Rsum, Rcount) = helper(node.right, 0, 0) 
     return (node.data + Lsum + Rsum, 1 + Lcount + Rcount) 
    (sum, count) = helper(tree, 0, 0) 
    return sum/count if count > 0 else None 

# your node class 
class Node (object): 
    def __init__(self, data, left, right): 
    self.data = data 
    self.left = left 
    self.right = right 

# make your tree 
tree = Node(5, Node(3, Node(2, None, None), None), Node(6, None, None)) 

print(avg(tree)) #=> 4.0 

# ensure that this works for an empty tree too (it does) 
print(avg(None)) #=> None 

을하여 실패한

---

직관

재귀는 우리가 이것에 대해 정말 좋은 직관 개발할 수 있습니다 - 특히 가 굵은 라인

을

(Lsum, Lcount) = helper(node.left, 0, 0) 
(Rsum, Rcount) = helper(node.right, 0, 0) 
return (node.data + Lsum + Rsum, 1 + Lcount + Rcount)

그 return은 retu 좌우 합계가 카운트위한

이다 불문 합,이 노드의 데이터 플러스 (sum, count)

• 터플을 RN은, (1)을 더한대로 좌우을이 노드 카운트 카운트가 이런 식으로 작성하여

을, 우리는 매우 명확하게 우리의 기능을 처리하는 두 경우를 볼 수 있습니다

노드 None 경우 1,515,
1. , 우리는 그렇지 않으면, 우리는 노드 data 카운트 의 합 및 1 기여 최종 계산
2. (0, 0)에 기여.

---

인라인 코드를 설명

# we only need to expose one function 
def avg (tree): 

    # helper isn't exposed outside of avg 
    # helper has stateful parameters 
    def helper (node, sum, count): 

    # helper is a recursive function, start with the base case of empty Node 
    if node is None: 
     # our base sum and count are 0 
     return (0, 0) 

    # process the Node 
    else: 

     # get L sum and count the same way we initialized helper with the tree 
     (Lsum, Lcount) = helper(node.left, 0, 0) 

     # do the same for the R side 
     (Rsum, Rcount) = helper(node.right, 0, 0) 

     # no reassignment of sum or count is necessary, 
     # simply recurse using the new state values of each 
     return (
     node.data + Lsum + Rsum, # sum equals this node plus L and R sums 
     1 + Lcount + Rcount  # count equals 1 plus L and R counts 
    ) 

    # always init the sum and count with 0 
    (sum, count) = helper(tree, 0, 0) 

    # don't divide by zero if the tree is empty; instead return None 
    return sum/count if count > 0 else None 

---

모든 중간 값 정리

은의이

,369 살펴 보자

(Lsum, Lcount) = helper(node.left, 0, 0) 
(Rsum, Rcount) = helper(node.right, 0, 0) 
return (node.data + Lsum + Rsum, 1 + Lcount + Rcount) 

나 같은 사람이라면 재 할당을 사용하여 다른 답변을 크게 개선 했음에도 불구하고 여전히 중간 값이 사용되고 있습니다. 우리가 이것을 약간 정리할 수 있다면 좋을 것입니다.

튜플 목록을 취할 수있는 함수가 있고 해당 위치에 모든 값을 추가하면 어떨까요?

// if only ... 
sum_tuples((0, 10), (1, 20), (2, 30)) 
# ... (0 + 1 + 2 , 10 + 20 + 30) 
#=> (3, 60) 

그 기능이 zip의 도움으로 작성하기 위해 실제로 매우 쉽게 밝혀졌습니다.이 기능은 우리의 avg 기능 이외의 장소에서 유용하므로 작업이 일반적이다, 그래서 나는 이제 별도

def sum_tuples (*xs): 
    return tuple(sum(x) for x in zip(*xs)) 

sum_tuples((0,10), (1,20), (2,30)) 
#=> (3, 60) 

그것을 정의가 avg에 미치는 영향을 살펴 보겠습니다 - 에서 더 이상 중간 값 (변경 굵은)

는 이전과 동일하게 작동 물론

def avg (tree): 
    def helper (node, sum, count): 
    if node is None: 
     return (0, 0) 
    else: 
     return sum_tuples( (node.data, 1), 
     helper(node.left, 0, 0), 
     helper(node.right, 0, 0) 
     ) 
    (sum, count) = helper(tree, 0, 0) 
    return sum/count if count > 0 else None

만 지금은 할 수있는 막으로 아름답다.

Answer 2

helper을 호출 할 때 반환 값을 사용하지 않습니다. 이들은 전체 트리의 값의 합을 결정하는 데 사용되어야한다

def helper(root, total=0, amount=0): 
    if root != None: 
     total += root.data 
     amount += 1 
     _, left_total, left_amount = helper(root.left, total, amount) 
     _, right_total, right_amount = helper(root.right, total, amount) 
     total += left_total 
     total += right_total 
     amount += left_amount 
     amount += right_amount 

    return (root, total, amount) 

다음 라인이 세 값의 각각에 helper 반환 값을 "언팩"

_, left_total, left_amount = helper(root.left, total, amount) 

첫 세 개의 값은 _에 할당되지만 무시됩니다 (이 경우 변수 _이 일반적으로 사용됩니다). left_total 및 left_amount이 반환 된 튜플의 두 번째 및 세 번째 값입니다.

Answer 3

def helper(root, total=0, amount=0): 
if root != None: 
    total += root.data 
    amount += 1 
    (_, total, amount) = helper(root.left, total, amount) 
    (_, total, amount) = helper(root.right, total, amount) 
return (root, total, amount) 

도우미 함수에 현재 합계와 양을 지정했지만 반환 값은 저장하지 않을 것입니다. 더 복잡성을 추가하는 재 할당을 사용할 필요가 없습니다 -