Giả sử chúng ta có một cây nhị phân; chúng ta phải tìm một danh sách có chứa trình duyệt của root dưới dạng danh sách. Như chúng ta đã biết, inorder traversal là một cách duyệt qua tất cả các nút trong một cây mà chúng ta -
-
Đi qua đệ quy cây con bên trái.
-
Đi ngang qua nút hiện tại.
-
Đệ quy duyệt qua cây con bên phải.
Chúng tôi phải cố gắng giải quyết vấn đề này theo kiểu lặp đi lặp lại.
Vì vậy, nếu đầu vào giống như
thì đầu ra sẽ là [12,13,4,16,7,14,22]
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
inorder:=một danh sách mới
-
stack:=một ngăn xếp trống
-
Làm những điều sau vô hạn, hãy làm
-
nếu root không null thì
-
đẩy root vào ngăn xếp
-
root:=left of root
-
-
ngược lại khi ngăn xếp không trống thì
-
root:=phần tử trên cùng của ngăn xếp và bật từ ngăn xếp
-
chèn giá trị của root vào cuối inorder
-
root:=right of root
-
-
nếu không,
-
đi ra từ vòng lặp
-
-
-
trả lại inorder
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
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))
Đầ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]