题目描述 给出一颗二叉树，请把它左右翻转。超级简单吧，max howell竟然不会写，然后被google直接拒掉。(然后，然后...自己上网查吧) 比如下面的树这样翻转，然后输出翻转后先序遍历顺序。 4 / \ 2 6 / \ / \ 1 3 5 7 (转换前先序遍历顺序为 4 2 1 3 6 5 7) 4 / \ 6 2 / \ / \ 7 5 3 1 (转换后先序遍历顺序为 4 6 7 5 2 3 1) 输入 第一行一个整数t(<=10)，表示有t组测试数据。 对于每组测试数据： 第一行两个整数n(<=8191)和d(1<=d<=13)，表示这棵树有n个结点(结点标号为1~n)，树有d层。 接下来d行： 第i行有2^(i-1)个整数，其中i行第j个a[i][j]的左儿子结点为a[i+1][j*2-1]右儿子为a[i+1][j*2](-1表示不存在该结点) 输出 对于每组数据输出一行为这颗树翻转后的先序遍历顺序。整数之间用空格隔开，最后一个整数后面没有空格。 样例输入 2 4 3 1

```python class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def invertTree(root): # 如果当前节点为空，直接返回 if not root: return None # 交换左右子树 root.left, root.right = root.right, root.left # 递归翻转左右子树 invertTree(root.left) invertTree(root.right) return root def preorderTraversal(root): # 先序遍历函数 if not root: return [] result = [] stack = [root] while stack: node = stack.pop() result.append(node.val) if node.right: stack.append(node.right) if node.left: stack.append(node.left) return result def buildTree(data): # 构建二叉树 if not data: return None nodes = [None if val == -1 else TreeNode(int(val)) for val in data] kids = nodes[::-1] root = kids.pop() for node in nodes: if node: if kids: node.left = kids.pop() if kids: node.right = kids.pop() return root def solve(t, test_cases): results = [] for n, d, tree_data in test_cases: # 构建树 tree = buildTree(tree_data) # 翻转树 inverted_tree = invertTree(tree) # 获取先序遍历结果 pre_order = preorderTraversal(inverted_tree) results.append(' '.join(map(str, pre_order))) return results # 读取输入 import sys input = sys.stdin.read data = input().split() index = 0 t = int(data[index]) test_cases = [] for _ in range(t): n = int(data[index + 1]) d = int(data[index + 2]) index += 3 tree_data = [] for i in range(d): row = list(map(int, data[index:index + 2 i])) index += 2 i tree_data.extend(row) test_cases.append((n, d, tree_data)) results = solve(t, test_cases) for result in results: print(result) ``` 需要注意的逻辑点： 1. 边界条件：确保在构建树时处理好 `-1` 表示的空节点。 2. 递归深度：由于树的最大层数 `d` 可以达到 13，递归调用可能较深，确保递归不会导致栈溢出。 3. 输入解析：输入数据的解析需要准确无误，特别是多组测试数据的处理，确保每一组数据的解析正确。 [2024-12-02 09:50:35 | AI写代码神器 | 613点数解答]