华为OD机试 - 创建二叉树（Java 2024 E卷 200分）

题目描述

给定一系列树状结构操作的问题，通过 Q 次查询还原树结构并输出结果。题目要求实现一个类 Solution，其方法 recoverTree 需要根据输入的操作数组 operations 还原树的结构，并返回树的根节点。每个操作 operations[i] = [height, index] 表示在高度为 height 的位置插入一个索引为 index 的节点。

• 树节点定义：

  • 每个节点 node 存在左子节点，则初始为 null。
  • 每个节点 node 存在右子节点，则初始为 null。
  • 每个节点存储一个高度值 height 和索引值 index。

• 输入要求：

  • height 和 index 初始为 0，并按计数递增。
  • index 存储节点的创建顺序。

• 注意事项：

  • 输入用例保证每次操作对应的节点已经存在。
  • 控制台输出的内容是根据还原后的树根节点，按照层次遍历方式 Q 次查询打印的结果。

输入输出示例

示例 1:
输入: operations = [[0, 0], [0, 1], [1, 1], [1, 0], [0, 0]]
输出: [0, 0, 1, 1, 0]
解释:

• [0, 0]：创建高度 0，索引 0 的节点，作为根节点。
• [0, 1]：创建高度 0，索引 1 的节点，插入到根节点的左子树（因为高度相同，按索引顺序）。
• [1, 1]：创建高度 1，索引 1 的节点，插入到根节点的右子树（高度更高）。
• [1, 0]：创建高度 1，索引 0 的节点，插入到根节点的左子树（高度更高）。
• [0, 0]：查询高度 0，索引 0 的节点，返回其值 0。

示例 2:
输入: operations = [[-1, 0], [1, 3], [null, 2]]
输出: [-1, 0, 1, 3, null, 2]
解释:

• [-1, 0]：创建高度 -1，索引 0 的节点，作为根节点。
• [1, 3]：创建高度 1，索引 3 的节点，插入到根节点的右子树（高度更高）。
• [null, 2]：查询高度 null，索引 2 的节点，返回 null。

解题思路

问题分析

题目要求根据一系列操作还原一棵树，并通过查询返回指定节点的值。核心在于：

1. 树的构建：根据 operations 数组中的 [height, index] 创建节点并插入树中。
2. 插入规则：高度决定节点的层级，索引决定插入顺序。
3. 查询操作：根据 [height, index] 找到对应节点并返回其值。

算法选择

1. 树结构：使用二叉树结构存储节点，每个节点包含 height 和 index，并有左右子节点。
2. 插入规则：
   • 如果高度相同，优先插入到左子树。
   • 如果高度更高，优先插入到右子树。
   • 如果高度更低，插入到左子树。
3. 层次遍历：在查询时，通过层次遍历找到目标节点。

步骤详解

1. 定义节点类：包含 height、index、左子节点和右子节点。
2. 构建树：
   • 遍历 operations，对于每个操作：
     • 如果 height 不为 null，创建新节点并插入树中。
     • 插入时，比较 height 和 index，决定插入到左子树还是右子树。
3. 查询节点：
   • 遍历 operations，对于查询操作（height 为 null），通过层次遍历找到目标节点并返回其值。
4. 返回结果：按照查询顺序返回结果数组。

代码实现

Java

class TreeNode {int height;int index;TreeNode left;TreeNode right;TreeNode(int height, int index) {this.height = height;this.index = index;this.left = null;this.right = null;}
}class Solution {public int[] recoverTree(int[][] operations) {TreeNode root = null;List<Integer> result = new ArrayList<>();// 构建树for (int[] op : operations) {int height = op[0];int index = op[1];// 如果 height 不为 null，插入节点if (height != Integer.MIN_VALUE) {TreeNode node = new TreeNode(height, index);if (root == null) {root = node;} else {insertNode(root, node);}}}// 查询节点for (int[] op : operations) {int height = op[0];int index = op[1];if (height == Integer.MIN_VALUE) {// 查询操作TreeNode target = findNode(root, index);if (target == null) {result.add(null);} else {result.add(target.height);}} else {result.add(height);}}// 转换为数组int[] res = new int[result.size()];for (int i = 0; i < result.size(); i++) {if (result.get(i) == null) {res[i] = Integer.MIN_VALUE; // 用 MIN_VALUE 表示 null} else {res[i] = result.get(i);}}return res;}private void insertNode(TreeNode root, TreeNode node) {TreeNode current = root;while (true) {if (node.height == current.height) {if (current.left == null) {current.left = node;break;} else {current = current.left;}} else if (node.height > current.height) {if (current.right == null) {current.right = node;break;} else {current = current.right;}} else {if (current.left == null) {current.left = node;break;} else {current = current.left;}}}}private TreeNode findNode(TreeNode root, int index) {if (root == null) return null;Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {TreeNode node = queue.poll();if (node.index == index) return node;if (node.left != null) queue.offer(node.left);if (node.right != null) queue.offer(node.right);}return null;}
}

Python

class TreeNode:def __init__(self, height, index):self.height = heightself.index = indexself.left = Noneself.right = Noneclass Solution:def recoverTree(self, operations):root = Noneresult = []# 构建树for height, index in operations:if height is not None:node = TreeNode(height, index)if root is None:root = nodeelse:self.insert_node(root, node)# 查询节点for height, index in operations:if height is None:target = self.find_node(root, index)result.append(target.height if target else None)else:result.append(height)return resultdef insert_node(self, root, node):current = rootwhile True:if node.height == current.height:if current.left is None:current.left = nodebreakelse:current = current.leftelif node.height > current.height:if current.right is None:current.right = nodebreakelse:current = current.rightelse:if current.left is None:current.left = nodebreakelse:current = current.leftdef find_node(self, root, index):if not root:return Nonefrom collections import dequequeue = deque([root])while queue:node = queue.popleft()if node.index == index:return nodeif node.left:queue.append(node.left)if node.right:queue.append(node.right)return None

C++

#include <vector>
#include <queue>
using namespace std;class TreeNode {
public:int height;int index;TreeNode* left;TreeNode* right;TreeNode(int h, int idx) : height(h), index(idx), left(nullptr), right(nullptr) {}
};class Solution {
public:vector<int> recoverTree(vector<vector<int>>& operations) {TreeNode* root = nullptr;vector<int> result;// 构建树for (const auto& op : operations) {int height = op[0];int index = op[1];if (height != INT_MIN) {TreeNode* node = new TreeNode(height, index);if (!root) {root = node;} else {insertNode(root, node);}}}// 查询节点for (const auto& op : operations) {int height = op[0];int index = op[1];if (height == INT_MIN) {TreeNode* target = findNode(root, index);if (target) {result.push_back(target->height);} else {result.push_back(INT_MIN);}} else {result.push_back(height);}}return result;}private:void insertNode(TreeNode* root, TreeNode* node) {TreeNode* current = root;while (true) {if (node->height == current->height) {if (!current->left) {current->left = node;break;} else {current = current->left;}} else if (node->height > current->height) {if (!current->right) {current->right = node;break;} else {current = current->right;}} else {if (!current->left) {current->left = node;break;} else {current = current->left;}}}}TreeNode* findNode(TreeNode* root, int index) {if (!root) return nullptr;queue<TreeNode*> q;q.push(root);while (!q.empty()) {TreeNode* node = q.front();q.pop();if (node->index == index) return node;if (node->left) q.push(node->left);if (node->right) q.push(node->right);}return nullptr;}
};

JavaScript

class TreeNode {constructor(height, index) {this.height = height;this.index = index;this.left = null;this.right = null;}
}/*** @param {number[][]} operations* @return {number[]}*/
var recoverTree = function(operations) {let root = null;let result = [];// 构建树for (let [height, index] of operations) {if (height !== null) {let node = new TreeNode(height, index);if (!root) {root = node;} else {insertNode(root, node);}}}// 查询节点for (let [height, index] of operations) {if (height === null) {let target = findNode(root, index);result.push(target ? target.height : null);} else {result.push(height);}}return result;function insertNode(root, node) {let current = root;while (true) {if (node.height === current.height) {if (!current.left) {current.left = node;break;} else {current = current.left;}} else if (node.height > current.height) {if (!current.right) {current.right = node;break;} else {current = current.right;}} else {if (!current.left) {current.left = node;break;} else {current = current.left;}}}}function findNode(root, index) {if (!root) return null;let queue = [root];while (queue.length) {let node = queue.shift();if (node.index === index) return node;if (node.left) queue.push(node.left);if (node.right) queue.push(node.right);}return null;}
};

复杂度分析

• 时间复杂度：O(Q * H)，其中 Q 是操作次数，H 是树的高度。每次插入和查询都需要遍历树的深度，平均情况下为 O(log Q)，最坏情况下（树退化为链）为 O(Q)。
• 空间复杂度：O(Q)。树中最多有 Q 个节点，存储树和队列的空间为 O(Q)。

测试用例示例

测试用例 1:
输入: operations = [[0, 0], [0, 1], [1, 1], [1, 0], [0, 0]]
预期输出: [0, 0, 1, 1, 0]
解释: 按照操作构建树，最后查询高度 0，索引 0 的节点，返回 0。

测试用例 2:
输入: operations = [[-1, 0], [1, 3], [null, 2]]
预期输出: [-1, 0, 1, 3, null, 2]
解释: 构建树后，查询索引 2 的节点，未找到，返回 null。

测试用例 3:
输入: operations = [[0, 0], [1, 1], [null, 1]]
预期输出: [0, 0, 1, 1]
解释: 构建树后，查询索引 1 的节点，返回高度 1。

问题总结

本题是一个树结构的构建和查询问题，核心在于根据高度和索引的规则插入节点，并通过层次遍历查询目标节点。算法的关键点包括：

1. 插入规则：高度决定插入方向，相同高度优先左子树。
2. 查询效率：通过层次遍历查找目标节点。
3. 边界处理：处理 null 查询和未找到节点的情况。

该算法适用于动态构建树并查询的场景，但在树退化为链时效率较低。可能的优化方向包括使用平衡树（如 AVL 树或红黑树）来降低树高，从而将时间复杂度优化到 O(Q * log Q)。在实际应用中，例如文件系统或组织结构管理，可以用类似方法动态构建和查询树结构。