Binary Tree Inorder Traversal

2980阅读 0评论2015-08-17 qinchaowhut
分类:C/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.  * Return an array of size *returnSize.
  11.  * Note: The returned array must be malloced, assume caller calls free().
  12.  */
  13. int* inorderTraversal(struct TreeNode* root, int* returnSize) {
  14.     struct TreeNode *sk[100];
  15.     int sp=0;
  16.     struct TreeNode *p=root;
  17.     int *arr=malloc(sizeof(int)*100);
  18.     *returnSize=0;
  19.     while(p||sp)
  20.     {
  21.         if(p)
  22.         {
  23.             sk[sp++]=p;
  24.             p=p->left;
  25.         }
  26.         else
  27.         {
  28.             p=sk[--sp];
  29.             arr[*returnSize]=p->val;
  30.             (*returnSize)++;
  31.             p=p->right;
  32.         }
  33.     }
  34.     return arr;
  35. }



上一篇:Binary Tree Postorder Traversal
下一篇:Single Number III