Binary Tree Postorder Traversal bằng Python

Giả sử chúng ta có một cây nhị phân. Chúng ta phải tìm duyệt thứ tự bài đăng của cây này bằng cách sử dụng phương pháp lặp lại. Vì vậy, nếu cây như -

Khi đó đầu ra sẽ là:[9,15,7,10, -10]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• nếu gốc là null, thì trả về mảng trống

• tạo một mảng ret

• stack:=xác định một ngăn xếp với cặp [root, 0]

• trong khi ngăn xếp không trống -

  • node:=top của ngăn xếp, sau đó xóa phần tử khỏi ngăn xếp.

  • nếu giá trị thứ hai của cặp nút là 0, thì

    • current:=giá trị đầu tiên của cặp nút

    • chèn một cặp (hiện tại, 1) vào ngăn xếp

    • nếu quyền hiện tại có -

      • chèn một cặp [bên phải dòng điện, 0] vào ngăn xếp

    • nếu còn lại hiện tại là hiện tại -

      • chèn một cặp [bên trái dòng điện, 0] vào ngăn xếp

  • Ngược lại, khi dữ liệu của cặp nút có giá trị đầu tiên không phải là 0, thì hãy chèn dữ liệu của giá trị đầu tiên của nút vào res

• trả lại res

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn -

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))

Đầu vào

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

Đầu ra

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