1、简言

最近秋招面试，发现有的公司考察二叉树方面的算法题时需要自己建立二叉树，因此写一下建立二叉树的步骤回忆一下。

2、思路

首先需要写出二叉树的结点结构：

struct TreeNode{
    int val;
    TreeNode *left;
    TreeNode *right;
    //列表初始化
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

其次递归建树：

• 函数返回值：返回建好的树根结点
• 函数参数：无，建树不需要参数（如果不需要通过传入数组建树的话）
• 函数体：首先输入根节点的值。然后开辟根节点。左右子树继续递归建树，递归出口就是输入结点值是-1时返回上一层。

TreeNode* createBinaryTree(){
    int val;
    cin >> val;
    if(val == -1){
        return NULL;
    }
    TreeNode *root = new TreeNode(val);
    root->left = createBinaryTree();
    root->right = createBinaryTree();
    return root;
}

3、完整代码

#include <iostream>
using namespace std;

struct TreeNode{
    int val;
    TreeNode *left;
    TreeNode *right;
    //列表初始化
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

//递归建立二叉树
TreeNode* createBinaryTree(){
    int val;
    cin >> val;
    if(val == -1){
        return NULL;
    }
    TreeNode *root = new TreeNode(val);
    root->left = createBinaryTree();
    root->right = createBinaryTree();
    return root;
}

//先序遍历打印二叉树
void preorder(TreeNode *root){
    if(root == NULL){
        return;
    }
    cout << root->val << " ";
    preorder(root->left);
    preorder(root->right);
}

int main()
{
    TreeNode *root = createBinaryTree();
    preorder(root);
    return 0;
}