二叉树的创建

二叉树是一种常见的树状数据结构，它的每个节点最多有两个子节点。二叉树的创建可以通过递归或非递归两种方法实现。

递归创建二叉树的方法如下：

1. 定义二叉树节点结构体：

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

2. 创建一个新节点，将其值设置为当前遍历到的值。

3. 递归创建左子树，将当前节点的左指针指向左子树的根节点。

4. 递归创建右子树，将当前节点的右指针指向右子树的根节点。

5. 返回当前节点。

代码如下：

TreeNode* createBinaryTree(vector<int>& nums, int index) {
    if (index >= nums.size() || nums[index] == -1) {
        return nullptr;
    }
    TreeNode* root = new TreeNode(nums[index]);
    root->left = createBinaryTree(nums, 2 * index + 1);
    root->right = createBinaryTree(nums, 2 * index + 2);
    return root;
}

其中，`nums` 是按照层序遍历顺序存储的二叉树节点值，`-1` 表示空节点，`index` 是当前遍历到的节点在 `nums` 中的索引。

非递归创建二叉树的方法需要借助栈来实现，具体过程如下：

1. 创建一个栈，将根节点入栈。

2. 循环遍历栈，每次取出栈顶节点，并将当前遍历到的值作为其左子节点的值，将其入栈。然后再取出栈顶节点，并将当前遍历到的值作为其右子节点的值，将其入栈。

3. 直到遍历完所有节点或者栈为空时，结束循环。

代码如下：

TreeNode* createBinaryTree(vector<int>& nums) {
    if (nums.empty()) {
        return nullptr;
    }
    TreeNode* root = new TreeNode(nums[0]);
    stack<TreeNode*> stk;
    stk.push(root);
    int i = 1;
    while (i < nums.size()) {
        TreeNode* node = stk.top();
        stk.pop();
        if (nums[i] != -1) {
            node->left = new TreeNode(nums[i]);
            stk.push(node->left);
        }
        ++i;
        if (i < nums.size() && nums[i] != -1) {
            node->right = new TreeNode(nums[i]);
            stk.push(node->right);
        }
        ++i;
    }
    return root;
}

其中，`nums` 的含义和递归创建方法相同。