leetcode105 从前序与中序遍历序列构造二叉树

前序遍历的第一个元素为根节点，中序遍历的根节点左侧是左子树，右侧是右子树。

在中序遍历中找到根节点，从而找到左右子树，知道左右子树的范围，从而前序遍历中的左右子树也就确定好了。然后分别对左右子树重复这个方式，直至结束。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        // 使用哈希表存储中序遍历中每个元素的索引，方便快速查找
        unordered_map<int, int> inorder_map;
        for (int i = 0; i < inorder.size(); i++) {
            inorder_map[inorder[i]] = i;
        }
        return buildTreeHelper(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1, inorder_map);
    }

private:
    TreeNode* buildTreeHelper(vector<int>& preorder, int pre_start, int pre_end, 
                            vector<int>& inorder, int in_start, int in_end, 
                            unordered_map<int, int>& inorder_map) {
        // 递归中止条件：树为空
        if (pre_start > pre_end || in_start > in_end) {
            return nullptr;
        }

        // 根节点的值为前序遍历的第一个元素值
        int rootVal = preorder[pre_start];
        // 创建根节点
        TreeNode* root = new TreeNode(rootVal);

        // 用根节点的值去中序数组中查找对应元素下标
        int midIndex = inorder_map[rootVal];

        // 计算左子树的长度
        int leftTreeSize = midIndex - in_start;

        // 递归构造左子树
        root->left = buildTreeHelper(preorder, pre_start + 1, pre_start + leftTreeSize,
                                    inorder, in_start, midIndex - 1, inorder_map);

        // 递归构造右子树
        root->right = buildTreeHelper(preorder, pre_start + leftTreeSize + 1, pre_end,
                                    inorder, midIndex + 1, in_end, inorder_map);

        return root;
    }
};

将 buildTreeHelper 定义为 private 是为了：

1. 封装实现细节，隐藏不必要的复杂性。

2. 防止外部代码误用。

3. 保持类的接口简洁清晰。

4. 提高代码的可维护性和可扩展性。

这是一种良好的编程实践，尤其是在设计类时，应该尽量遵循这种原则。

如果buildTreeHelper 是 public 的，外部代码可以直接调用它。由于 buildTreeHelper 是一个递归辅助函数，它依赖于特定的参数范围（例如 pre_start、pre_end、in_start、in_end），如果外部代码错误地调用它，可能会导致程序崩溃或产生错误的结果。