Binary Tree Inorder Traversal ใน Python - ท่องต้นไม้แบบทวิภาค Inorder

สมมติว่าเรามี binary tree เราต้องท่องต้นไม้นี้ด้วย inorder traversal scheme โดยไม่ใช้ recursion ตัวอย่าง ถ้าต้นไม้เป็นแบบนี้:

ลำดับการท่องจะเป็น [2, 5, 7, 10, 15, 20]

ขั้นตอนการทำงาน (Iterative with Stack)

1. สร้างอาร์เรย์ res และ stack ตั้งค่า curr := root
2. รันลูปไม่รู้จบ:
   • วนลูป while current is not null:
     • push curr ลง stack, ตั้ง curr := left of curr
   • ถ้าความยาวของ stack = 0 ให้คืนค่า res
   • node := popped element from stack
   • เพิ่มค่า node ลงใน res
   • curr := right of curr

ตัวอย่างโค้ด

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:
            temp.left = TreeNode(data)
            break
        else:
            que.append(temp.left)
        if not temp.right:
            temp.right = TreeNode(data)
            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 inorderTraversal(self, root):
        res, stack = [], []
        current = root
        while True:
            while current:
                stack.append(current)
                current = current.left
            if len(stack) == 0:
                return res
            node = stack[-1]
            stack.pop(len(stack)-1)
            if node.data is not None:
                res.append(node.data)
            current = node.right
        return res

ob1 = Solution()
root = make_tree([10, 5, 15, 2, 7, None, 20])
print(ob1.inorderTraversal(root))

อินพุต

[10,5,15,2,7,null,20]

เอาต์พุต

[2, 5, 7, 10, 15, 20]