[数据结构与算法]leetcode94.二叉树的中序遍历

1：递归代码

void midTraversal(struct TreeNode *root,int *ret,int *returnSize)
 {
     if(root)
     {

         midTraversal(root->left,ret,returnSize);//先中序访问左子树
         ret[(*returnSize)++]=root->val;//中序访问左子树之后，访问并计入数组根节点
         midTraversal(root->right,ret,returnSize);//最后中序访问右子树
     }
 }
int* inorderTraversal(struct TreeNode* root, int* returnSize){
    int *ret=(int *)malloc(sizeof(int)*100);
    *returnSize=0;
    midTraversal(root,ret,returnSize);
    return ret;
}

2：迭代思想

1：因为中序遍历是先处理左子树，然后处理中间节点，最后处理右子树。左右子树也是相同的处理方式。

2：其实迭代要做的只有两件事，：把延迟处理的先放入栈中，先处理的后放入栈中；要处理的弹出栈。

3：最后处理的是中间节点和右子树，应该先将右子树放入栈中，再将根节点放入栈中，但是右子树明显是可以用根节点表示的，如果我们只将根节点放入栈中，当根节点出栈处理的时候，将用根节点表示的右子树放入栈中，是不是也达到了先处理根节点，再处理右子树的目的。

4：我们应该最后将左子树放入栈中（注意左子树用左子树的根节点代替）,现在栈顶是左子树的根节点，其实将左子树视为一个新的树New，放入左子树的根节点，是不是相当于将新树New的根节点和右子树放入栈了，现在再放入新树New的左子树再放入栈是不是就行了，现在栈顶的节点又可以视为一个新的树的根节点和右子树，在将其左子树放入就行，以此类推。（空节点永远不入栈）。

5：注：栈中的每一个节点都视为根节点和右子树，弹出后先处理完根节点，再将用根节点表示的右子树入栈，这样就达到了左，中，右的处理顺序。

int* inorderTraversal(struct TreeNode* root, int* returnSize){
    int *ret=(int *)malloc(sizeof(int)*101);
    *returnSize=0;
    struct TreeNode *stack[100];
    int top=0;
    if(root==NULL)
    {
        return ret;
    }
    stack[0]=root;
    while(top>=0)
    {
        while(stack[top]->left!=NULL)//向左走到尽头
        {
            struct TreeNode *temp= stack[top]->left;
            stack[++top]=temp;
        }
        while(top>=0)
        {
        struct TreeNode *temp1= stack[top--];//弹出的节点就是要放入数组的节点
        ret[(*returnSize)++]=temp1->val;
        if(temp1->right!=NULL)
        {//如果弹出的节点右子树不为空，则按上面的循环继续处理
            stack[++top]=temp1->right;
            break;
        }
        }
    }
    return ret;
}