Computer >> 컴퓨터 >  >> 프로그램 작성 >> C++

Python 프로그래밍의 이진 트리 후위 순회


바이너리 트리가 있다고 가정합니다. 반복적 접근을 사용하여 이 트리의 사후 순회를 찾아야 합니다. 트리가 다음과 같다면 -

Python 프로그래밍의 이진 트리 후위 순회

그러면 출력은 다음과 같습니다. [9,15,7,10,-10]

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

  • 루트가 null이면 빈 배열을 반환합니다.

  • ret 배열 생성

  • stack :=[root, 0] 쌍으로 스택 정의

  • 스택이 비어 있지 않은 동안 -

    • node :=스택의 맨 위, 스택에서 요소 삭제

    • 노드 쌍의 두 번째 값이 0이면

      • 현재 :=노드 쌍의 첫 번째 값

      • 스택에 쌍(현재, 1) 삽입

      • 현재의 권리가 있는 경우

        • [현재 오른쪽, 0] 쌍을 스택에 삽입

      • 전류의 왼쪽이 있는 경우 -

        • [현재 왼쪽, 0] 쌍을 스택에 삽입

    • 그렇지 않으면 첫 번째 값 노드 쌍의 데이터가 0이 아닌 경우 노드의 첫 번째 값 데이터를 res

      에 삽입합니다.
  • 반환 해상도

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

class TreeNode:
def __init__(self, data, left = None, right = None):
   self.data = data
   self.left = left
   self.right = right
def insert(temp,data):
   que = []
   que.append(temp)
   while (len(que)):
      temp = que[0]
      que.pop(0)
      if (not temp.left):
         if data is not None:
            temp.left = TreeNode(data)
         else:
            temp.left = TreeNode(0)
         break
      else:
         que.append(temp.left)
      if (not temp.right):
         if data is not None:
            temp.right = TreeNode(data)
         else:
            temp.right = TreeNode(0)
         break
      else:
         que.append(temp.right)
def make_tree(elements):
   Tree = TreeNode(elements[0])
   for element in elements[1:]:
      insert(Tree, element)
   return Tree
class Solution(object):
   def postorderTraversal(self, root):
      if not root:
         return []
      res = []
      stack = [[root,0]]
      while stack:
         node = stack[-1]
         stack.pop()
         if node[1]== 0 :
            current = node[0]
            stack.append([current,1])
            if current.right:
               stack.append([current.right,0])
            if current.left:
               stack.append([current.left,0])
         else:
            if node[0].data != 0:
               res.append(node[0].data)
      return res
ob = Solution()
root = make_tree([-10,9,10,None,None,15,7])
print(ob.postorderTraversal(root))

입력

[-10,9,10,None,None,15,7]

출력

[9, 15, 7, 10, -10]