LeetCode ：中序遍历二叉树(迭代）

慵懒的勤快孩儿

若树为空，则空操作返回，否则从根结点开始（注意并不是先访问根结点），中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树。

C语言实现：

/**
 * 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().
 */

int* inorderTraversal(struct TreeNode* root, int* returnSize){
    struct TreeNode *stack[1000];
    int top = -1;
    int *result = (int *)malloc(sizeof(int)*100);
    int i = 0;
    while(true)
    {
        while(root)
        {
            stack[++top] = root;
            root = root->left; 
            /*
            从根节点遍历左子树，一直遍历到底
            并将遍历到的结点存入数组(栈)内备用
            */
        }
        if(top == -1){
            * returnSize = i;
            return result;
                //top == -1,栈为空，即全部遍历完毕，输出数据
        }
        root = stack[top--];
        result[i++] = root->val;
        root = root->right;
        /*
        从左子树最底开始保存结点数据，每次遍历都查看有无右孩子
              如果有右孩子，上面执行上面while
        如果没有，则接续从stack栈顶弹出结点，将结点val存入数组
       */
    }
}