Giả sử ta có một cây nhị phân, ta cần tạo một chuỗi gồm dấu ngoặc đơn và số nguyên từ cây nhị phân theo cách duyệt tiền thứ tự (preorder). Nút null sẽ được biểu diễn bằng cặp ngoặc đơn rỗng "()". Và ta cần bỏ qua tất cả các cặp ngoặc đơn rỗng không ảnh hưởng đến mối quan hệ ánh xạ một-một giữa chuỗi và cây nhị phân gốc.
Ví dụ, nếu đầu vào là như hình:
thì đầu ra sẽ là 5(6()(8))(7)
Để giải quyết, ta thực hiện các bước sau:
- ans := chuỗi rỗng
- Định nghĩa hàm pot(). Nhận node, s
- Nếu là null, thì:
- Trả về chuỗi rỗng
- Nếu left hoặc right của node là null, thì:
- Trả về node.data
- ss := node.data
- Nếu node.left không phải null, thì:
- ss := ss nối '(' nối pot(node.left, chuỗi rỗng) nối ')'
- Ngược lại:
- ss := ss nối '()'
- Nếu node.right không phải null, thì:
- ss := ss nối '(' nối pot(node.right, chuỗi rỗng) nối ')'
- Trả về ss
- Từ phương thức chính thực hiện:
- Trả về pot(t, chuỗi rỗng)
Hãy xem triển khai sau để hiểu rõ hơn:
Ví dụ
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: def tree2str(self, t: TreeNode): ans = '' def pot(node, s): if node == None or node.data == 0: return '' if node.left == node.right == None: return str(node.data) ss = str(node.data) if node.left != None: ss = ss + '(' + pot(node.left, '') + ')' else: ss = ss + '()' if node.right != None: ss = ss + '(' + pot(node.right, '') + ')' return ss return pot(t, '') ob = Solution() root = make_tree([5,6,7,None,8]) print(ob.tree2str(root))Đầu vào
[5,6,7,None,8]
Đầu ra
5(6()(8))(7)