Giả sử có hai chuỗi duyệt Preorder và Postorder, ta phải tạo cây nhị phân từ hai chuỗi này. Nếu chuỗi là [1,2,4,5,3,6,7], [4,5,2,6,7,3,1], kết quả là cây như hình.
Để giải quyết, ta làm theo các bước −
- ans := tạo TreeNode với giá trị pre[0], stack := stack rỗng, push ans
- i := 1, j := 0
- khi i < len(pre) và j < len(post)
- nếu stack[-1].data == post[j], tăng j 1, pop stack, continue
- node := tạo TreeNode với giá trị pre[i]
- nếu left của stack[-1] rỗng, gán left = node, ngược lại right = node
- push node vào stack
- tăng i 1
- trả về ans
Xem triển khai sau −
Ví dụ
class TreeNode: def __init__(self, data, left = None, right = None): self.data = data self.left = left self.right = right def height(root): if root is None: return 0 else : l_height = height(root.left) r_height = height(root.right) if l_height > r_height : return l_height+1 else: return r_height+1 def print_given_level(root, level): if root is None: return if level == 1: print(root.data,end = ',') elif level > 1 : print_given_level(root.left , level-1) print_given_level(root.right , level-1) def level_order(root): print('[', end = '') h = height(root) for i in range(1, h+1): print_given_level(root, i) print(']') class Solution(object): def constructFromPrePost(self, pre, post): """ :type pre: List[int] :type post: List[int] :rtype: TreeNode """ ans = TreeNode(pre[0]) stack = [ans] i = 1 j = 0 while i < len(pre) and j < len(post): if stack[-1].data == post[j]: j+=1 stack.pop(-1) continue node = TreeNode(pre[i]) if not stack[-1].left: stack[-1].left = node else: stack[-1].right = node stack.append(node) i+=1 return ans ob = Solution() pre = [1,2,4,5,3,6,7] post = [4,5,2,6,7,3,1] tree = ob.constructFromPrePost(pre, post) level_order(tree)Đầu vào
[1,2,4,5,3,6,7] [4,5,2,6,7,3,1] pre = [1,2,4,5,3,6,7] post = [4,5,2,6,7,3,1]
Kết quả
[1,2,3,4,5,6,7,]