1 from collections import deque 2 import sys 3 4 n = int(sys.stdin.readline()) 5 nodes = [()] * (n + 1) # 节点从1到n 6 7 for i in range(1, n + 1): 8 left, right = map(int, sys.stdin.readline().split()) 9 nodes[i] = (left, right) 10 11 result = [] 12 queue = deque([1]) 13 14 while queue: 15 level_size = len(queue) 16 for i in range(level_size): 17 current = queue.popleft() 18 if i == level_size - 1: 19 result.append(str(current)) 20 left, right = nodes[current] 21 if left != -1: 22 queue.append(left) 23 if right != -1: 24 queue.append(right) 25 26 print(' '.join(result))
1 class Node: 2 def __init__(self, value): 3 self.key = value 4 self.left = None 5 self.right = None 6 7 def depth(node): 8 if node: 9 return max(depth(node.left), depth(node.right)) + 1 10 else: 11 return 0 12 13 n = int(input()) 14 nums= [Node(i) for i in range(1, n + 1)] 15 for i in range(n): 16 a, b = map(int, input().split()) 17 if a != -1: 18 nums[i].left = nums[a - 1] 19 if b != -1: 20 nums[i].right = nums[b - 1] 21 22 ans = depth(nums[0]) 23 print(ans)
This code defines a TreeNode class representing a node in a binary tree and implements functions to build a binary tree from inorder and postorder traversal sequences and perform a preorder traversal on the tree.
1. The `TreeNode` class has attributes `val`, `left`, and `right` representing the node value and left and right child nodes respectively.
2. The `build_tree` function takes two input lists `inorder` and `postorder` representing the inorder and postorder traversal sequences of a binary tree respectively. It recursively constructs the binary tree using the given traversal sequences and returns the root node of the constructed tree.
3. The `pre_order_traversal` function performs a preorder traversal on the binary tree starting from the given node. It appends the value of each node to the `result` list in preorder traversal order.
4. The script reads two lines of input containing space-separated integers representing the inorder and postorder traversal sequences of a binary tree.
5. The script then builds a binary tree using the `build_tree` function with the provided inorder and postorder sequences.
6. Finally, it performs a preorder traversal on the constructed binary tree starting from the root node and prints the node values in preordered sequence separated by spaces.
Overall, this code snippet efficiently constructs a binary tree from the inorder and postorder traversal sequences and performs a preorder traversal on the constructed tree, demonstrating an understanding of tree construction and traversal algorithms.
1 class TreeNode: 2 def __init__(self, val): 3 self.val = val 4 self.left = None 5 self.right = None 6 7 def build_tree(inorder, postorder): 8 if not inorder: 9 return None 10 root_val = postorder[-1] 11 root = TreeNode(root_val) 12 root_idx = inorder.index(root_val) 13 left_in = inorder[:root_idx] 14 right_in = inorder[root_idx+1:] 15 left_size = len(left_in) 16 left_post = postorder[:left_size] 17 right_post = postorder[left_size:-1] 18 root.left = build_tree(left_in, left_post) 19 root.right = build_tree(right_in, right_post) 20 return root 21 22 def pre_order_traversal(node, result): 23 if node: 24 result.append(str(node.val)) 25 pre_order_traversal(node.left, result) 26 pre_order_traversal(node.right, result) 27 28 # 读取输入 29 in_order = list(map(int, input().split())) 30 post_order = list(map(int, input().split())) 31 32 # 构建二叉树 33 root = build_tree(in_order, post_order) 34 35 # 进行前序遍历 36 result = [] 37 pre_order_traversal(root, result) 38 39 # 输出结果 40 print(' '.join(result))
1 import sys 2 from math import comb 3 4 def count_degrees(pre, post, pre_start, pre_end, post_start, post_end, degrees): 5 if pre_start == pre_end and post_start == post_end: 6 return 7 else: 8 current_pre = pre_start + 1 9 current_post = post_start 10 length = 0 11 branch_count = 0 12 while current_post < post_end: 13 while (current_post + length <= post_end) and (pre[current_pre] != post[current_post + length]): 14 length += 1 15 branch_count += 1 16 count_degrees(pre, post, current_pre, current_pre + length, current_post, current_post + length, degrees) 17 current_pre = current_pre + length + 1 18 current_post = current_post + length + 1 19 length = 0 20 degrees.append(branch_count) 21 22 def calculate_combinations(m, n): 23 return comb(m, n) 24 25 def main(): 26 while True: 27 line = sys.stdin.readline() 28 if not line or line.strip() == '0': 29 break 30 parts = line.strip().split() 31 m = int(parts[0]) 32 pre = parts[1] 33 post = parts[2] 34 branches = [] 35 count_degrees(pre, post, 0, len(pre)-1, 0, len(post)-1, branches) 36 result = 1 37 for cnt in branches: 38 result *= calculate_combinations(m, cnt) 39 print(result) 40 41 if __name__ == "__main__": 42 main()