首先什么是树？树是计算机科学中最重要的数据结构之一，它模拟了现实世界中树状的层次结构关系。

树基本概念

树是由节点和边组成的非线性数据结构，具有以下特点：

• 有且仅有一个根节点（root）
• 除根节点外，每个节点都有且仅有一个父节点
• 节点间不能形成环路
• 从根节点到任意节点都有唯一路径

树的存储方式

链式存储：使用指针连接节点

cstruct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
};

基本操作

遍历方式：

• 前序遍历：根 → 左 → 右
• 中序遍历：左 → 根 → 右
• 后序遍历：左 → 右 → 根
• 层序遍历：按层次从上到下，从左到右

基本操作：插入、删除、查找、计算高度、判断平衡等

有了上面的基础后便可以尝试做题了。

二叉树的中序遍历

题目描述：给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

示例 1：
输入：root = [1,null,2,3]
输出：[1,3,2]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

提示：

树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100

解题思路

递归法
1,结束条件 root==NULL 则返回
2,递归左支
3,处理当前节点
4,递归右支

代码实现

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
void visit(struct TreeNode* root, int* returnSize, int* ret){
    //节点为空时返回
    if(root == NULL){
        return;
    }
    //递归处理左子树
    if(root->left != NULL){
        visit(root->left, returnSize, ret);
    }
    //处理当前节点
    ret[*returnSize] = root->val;
    (*returnSize)++;
    //递归处理右子树
    if(root->right != NULL){
        visit(root->right, returnSize, ret);
    }
}


int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    // 初始数组
    int* ret = (int*)malloc(100*sizeof(int));
    *returnSize = 0;
    // 根节点为空时直接返回
    if(root == NULL)
        return ret;
    visit(root, returnSize, ret);
    return ret;
}

先序和后序遍历的方法也与此类似，除了递归，用迭代来解决该问题也是不错的选择

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

//方法二：迭代法
//1,遍历节点A，将节点压入栈中，
//2,遍历A的左支，
//3,A出栈，访问A
//4,遍历A的右支
int* inorderTraversal(struct TreeNode* root, int* returnSize){
    int     iMax        = 100;
    int     iTop        = 0;
    int*    pRet        = NULL;
    int     iRetSize    = 0;

    struct TreeNode*    pTmp    = root;
    struct TreeNode*    pStrTreeBuf[iMax];       //建立节点指针数组，模拟栈保存节点

    pRet = (int*)malloc(sizeof(int) * iMax);
    memset(pRet, 0x00, sizeof(int) * iMax);

    while((pTmp != NULL) || (iTop != 0))
    {
        while(pTmp != NULL)
        {
            //1,遍历节点，将检点压入栈中
            pStrTreeBuf[iTop] = pTmp;
            iTop += 1;

            //2,遍历左支
            pTmp = pTmp->left;
        }

        //3,出栈，访问节点
        iTop -= 1;
        pTmp = pStrTreeBuf[iTop];
        pRet[iRetSize] = pTmp->val;
        iRetSize += 1;

        //4,遍历右支
        pTmp = pTmp->right;
    }

    //5,返回
    *returnSize = iRetSize;
    return pRet;
}