Python에서 이진 트리의 각 대각선 경로 요소의 합을 찾는 프로그램

이진 트리가 있다고 가정하고 오른쪽 위에서 시작하여 트리의 각 대각선의 합을 찾아야 합니다.

따라서 입력이 다음과 같으면

대각선이 [12,15], [8,10],[3]이므로 출력은 [27, 18, 3]이 됩니다. 따라서 합계 값은 [27, 18, 3]

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

함수 traverse() 를 정의합니다. 이것은 노드, numLeft, 출력

• 노드가 null이면

  • 반환

• numLeft>=출력 크기인 경우

  • 출력 끝에 노드의 데이터 삽입

• 그렇지 않으면

  • output[numLeft] :=output[numLeft] + 노드의 데이터

• 노드의 왼쪽이 null이 아니면

  • 트래버스(노드 왼쪽, numLeft+1, 출력)

• 노드의 오른쪽이 null이 아니면

  • traverse(노드의 오른쪽, numLeft, 출력)

• 기본 방법에서 다음을 수행하십시오 -

• 출력 :=새 목록

• 트래버스(루트, 0, 출력)

• 반환 출력

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.data = data
      self.left = left
      self.right = right
class Solution:
   def solve(self, root):
      output = []
      def traverse(node, numLeft, output):
         if not node:
            return
         if numLeft >= len(output):
            output.append(node.data)
         else:
            output[numLeft] += node.data
         if node.left:
            traverse(node.left, numLeft+1, output)
         if node.right:
            traverse(node.right, numLeft, output)
      traverse(root, 0, output)
      return output
ob = Solution()
root = TreeNode(12)
root.left = TreeNode(8)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(10)
print(ob.solve(root))

입력

root = TreeNode(12)
root.left = TreeNode(8)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(10)

출력

[27, 18, 3]