Chương trình duyệt Inorder cây nhị phân không đệ quy trong Python

Cho cây nhị phân, trả về danh sách duyệt inorder (trái - gốc - phải) bằng phương pháp lặp (iterative) thay vì đệ quy.

Ví dụ: cây như hình → [12, 13, 4, 16, 7, 14, 22].

Giải thuật (Stack mô phỏng đệ quy)

1. Khởi tạo , .
2. Vòng lặp vô tận:
   • Nếu không None: push vào stack, .
   • Ngược lại nếu stack không rỗng: pop , thêm vào , .
   • Ngược lại: break.
3. Trả về .

Ví dụ minh họa

class TreeNode:
    def __init__(self, value):
        self.val = value
        self.left = None
        self.right = None

class Solution:
    def solve(self, root):
        inorder = []
        stack = []
        while True:
            if root:
                stack.append(root)
                root = root.left
            elif stack:
                root = stack.pop()
                inorder.append(root.val)
                root = root.right
            else:
                break
        return inorder

ob = Solution()
root = TreeNode(13)
root.left = TreeNode(12)
root.right = TreeNode(14)
root.right.left = TreeNode(16)
root.right.right = TreeNode(22)
root.right.left.left = TreeNode(4)
root.right.left.right = TreeNode(7)
print(ob.solve(root))  # Output: [12, 13, 4, 16, 7, 14, 22]

Đầu vào

root = TreeNode(13) root.left = TreeNode(12) root.right = TreeNode(14) root.right.left = TreeNode(16) root.right.right = TreeNode(22) root.right.left.left = TreeNode(4) root.right.left.right = TreeNode(7)

Đầu ra

[12, 13, 4, 16, 7, 14, 22]