Giả sử chúng ta có cây nhị phân, chúng ta phải hiển thị các giá trị của mỗi cấp bằng cách luân phiên từ trái sang phải và từ phải sang trái.
Vì vậy, nếu đầu vào giống như
thì đầu ra sẽ là [5, -10, 4, -2, -7, 15]
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
nếu root là null thì
-
trả lại một danh sách mới
-
-
s1:=một danh sách ban đầu chèn root
-
s2:=một danh sách mới
-
res:=một danh sách mới
-
trong khi s1 không trống hoặc s2 không trống, thực hiện
-
trong khi s1 không trống, thực hiện
-
node:=xóa phần tử cuối cùng khỏi s1
-
nếu bên trái của nút không rỗng, thì
-
chèn bên trái của nút ở cuối s2
-
-
nếu bên phải của nút không rỗng, thì
-
chèn bên phải của nút ở cuối s2
-
-
chèn giá trị của nút vào cuối res
-
-
trong khi s2 không trống, thực hiện
-
node:=xóa phần tử cuối cùng khỏi s2
-
nếu bên phải của nút không rỗng, thì
-
chèn vào bên phải của nút ở cuối s1
-
-
nếu bên trái của nút không trống, thì
-
chèn bên trái của nút ở cuối s1
-
-
chèn giá trị của nút vào cuối res
-
-
-
trả lại res
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, data, left = None, right = None): self.val = data self.left = left self.right = right class Solution: def solve(self, root): if not root: return [] s1 = [root] s2 = [] res = [] while s1 or s2: while s1: node = s1.pop() if node.left: s2.append(node.left) if node.right: s2.append(node.right) res.append(node.val) while s2: node = s2.pop() if node.right: s1.append(node.right) if node.left: s1.append(node.left) res.append(node.val) return res ob = Solution() root = TreeNode(5) root.left = TreeNode(4) root.right = TreeNode(-10) root.left.left = TreeNode(-2) root.right.left = TreeNode(-7) root.right.right = TreeNode(15) print(ob.solve(root))
Đầu vào
root = TreeNode(5) root.left = TreeNode(4) root.right = TreeNode(-10) root.left.left = TreeNode(-2) root.right.left = TreeNode(-7) root.right.right = TreeNode(15)
Đầu ra
[5, -10, 4, -2, -7, 15]