首页华为od机试真题-数组二叉树

华为od机试真题-数组二叉树

时间: 2025-01-10 15:45:00 浏览: 136

### 华为OD机试中的数组与二叉树题目解析 #### 题目描述给定一个整数数组 `nums`，其中第一个元素代表根节点的值，后续元素按照完全二叉树的方式存储。对于任意索引 `i` (从1开始)，其左子节点位于位置 `2*i` 而右子节点则处于 `2*i + 1` 的位置[^2]。 #### 解决方案概述为了处理这类问题，可以采用递归的方法遍历这棵由数组构建起来的二叉树结构，并执行所需的操作。下面将以 Python 实现为例展示如何创建一棵基于输入数组的二叉树并对其进行前序遍历： ```python class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def array_to_binary_tree(nums): if not nums or nums[0] is None: return None root = TreeNode(nums[0]) queue = [root] i = 1 while i < len(nums): current_node = queue.pop(0) # 左孩子 if i < len(nums) and nums[i] is not None: current_node.left = TreeNode(nums[i]) queue.append(current_node.left) i += 1 # 右孩子 if i < len(nums) and i < len(nums) and nums[i] is not None: current_node.right = TreeNode(nums[i]) queue.append(current_node.right) i += 1 return root def preorder_traversal(root): result = [] stack = [root] while stack: node = stack.pop() if node: result.append(node.val) stack.append(node.right) stack.append(node.left) return result if __name__ == "__main__": test_array = [1, 2, 3, 4, 5, 6, 7] tree_root = array_to_binary_tree(test_array) print(preorder_traversal(tree_root)) ``` 此代码片段展示了如何将一个列表转换成对应的二叉树对象以及怎样通过栈来实现非递归版本的先序遍历算法。

阅读全文