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

慵懒的勤快孩儿

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

C语言实现：

1. /**
   
2. * Definition for a binary tree node.
   
3. * struct TreeNode {
   
4. *     int val;
   
5. *     struct TreeNode *left;
   
6. *     struct TreeNode *right;
   
7. * };
   
8. */
   
9. 
   
10. 
    
11. /**
    
12. * Note: The returned array must be malloced, assume caller calls free().
    
13. */
    
14. 
    
15. int* inorderTraversal(struct TreeNode* root, int* returnSize){
    
16.     struct TreeNode *stack[1000];
    
17.     int top = -1;
    
18.     int *result = (int *)malloc(sizeof(int)*100);
    
19.     int i = 0;
    
20.     while(true)
    
21.     {
    
22.         while(root)
    
23.         {
    
24.             stack[++top] = root;
    
25.             root = root->left;
    
26.             /*
    
27.             从根节点遍历左子树，一直遍历到底
    
28.             并将遍历到的结点存入数组(栈)内备用
    
29.             */
    
30.         }
    
31.         if(top == -1){
    
32.             * returnSize = i;
    
33.             return result;
    
34.                 //top == -1,栈为空，即全部遍历完毕，输出数据
    
35.         }
    
36.         root = stack[top--];
    
37.         result[i++] = root->val;
    
38.         root = root->right;
    
39.         /*
    
40.         从左子树最底开始保存结点数据，每次遍历都查看有无右孩子
    
41.               如果有右孩子，上面执行上面while
    
42.         如果没有，则接续从stack栈顶弹出结点，将结点val存入数组
    
43.        */
    
44.     }
    
45. }
    

复制代码