華為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。

解題思路

問題分析

題目要求根據一系列操作還原一棵樹，并通過查詢返回指定節點的值。核心在于：

樹的構建：根據 operations 數組中的 [height, index] 創建節點并插入樹中。
插入規則：高度決定節點的層級，索引決定插入順序。
查詢操作：根據 [height, index] 找到對應節點并返回其值。

算法選擇

樹結構：使用二叉樹結構存儲節點，每個節點包含 height 和 index，并有左右子節點。
插入規則：
- 如果高度相同，優先插入到左子樹。
- 如果高度更高，優先插入到右子樹。
- 如果高度更低，插入到左子樹。
層次遍歷：在查詢時，通過層次遍歷找到目標節點。

步驟詳解

定義節點類：包含 height、index、左子節點和右子節點。
構建樹：
- 遍歷 operations，對于每個操作：
  - 如果 height 不為 null，創建新節點并插入樹中。
  - 插入時，比較 height 和 index，決定插入到左子樹還是右子樹。
查詢節點：
- 遍歷 operations，對于查詢操作（height 為 null），通過層次遍歷找到目標節點并返回其值。
返回結果：按照查詢順序返回結果數組。

代碼實現

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;}
};