朝阳无限好 - Morning Sun Community

 找回密码
 注册
查看: 198|回复: 2

[中等] 94. 二叉树的中序遍历

[复制链接]
发表于 2020-4-7 22:37:52 | 显示全部楼层 |阅读模式
给定一个二叉树,返回它的中序 遍历。

示例:

输入: [1,null,2,3]
   1
    \
     2
    /
   3

输出: [1,3,2]
进阶: 递归算法很简单,你可以通过迭代算法完成吗?

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/binary-tree-inorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
 楼主| 发表于 2020-4-7 22:38:17 | 显示全部楼层
  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. * Note: The returned array must be malloced, assume caller calls free().
  11. */
  12. int* inorderTraversal(struct TreeNode* root, int* returnSize){
  13.     struct TreeNode* st[1000]={0};      //数组模拟栈
  14.     int* nums = malloc(sizeof(int)*1000);
  15.     int p=-1,index=0;               //p代表栈指针
  16.     while(root!=NULL||p!=-1)
  17.     {
  18.         while(root!=NULL)               //持续向左走,走到不能走
  19.         {
  20.             st[++p] = root;           //进栈
  21.             root=root->left;
  22.         }
  23.         if(p!=-1)                     
  24.         {
  25.             root=st[p--];             //出栈
  26.             nums[index++]=root->val;    //存入当前节点值
  27.             root=root->right;           
  28.         }
  29.             
  30.     }
  31.     *returnSize=index;
  32.     return nums;
  33. }
复制代码
执行结果:通过
显示详情

执行用时 :0 ms, 在所有 C 提交中击败了100.00%的用户
内存消耗 :5.9 MB, 在所有 C 提交中击败了100.00%的用户
回复 支持 反对

使用道具 举报

 楼主| 发表于 2020-4-7 22:46:39 | 显示全部楼层
  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. void step(struct TreeNode *root, int *result, int *rSize)
  10. {
  11.     if(!root) return;
  12.    
  13.     step(root->left, result, rSize);
  14.     result[*rSize] = root->val;
  15.     (*rSize)++;
  16.     step(root->right, result, rSize);
  17. }

  18. /**
  19. * Note: The returned array must be malloced, assume caller calls free().
  20. */
  21. int* inorderTraversal(struct TreeNode* root, int* returnSize){
  22.     int *result = (int *)malloc(sizeof(int) * 1000);
  23.     int rSize = 0;
  24.     step(root, result, &rSize);
  25.     *returnSize = rSize;
  26.     return result;
  27. }


复制代码
执行结果:通过
显示详情

执行用时 :0 ms, 在所有 C 提交中击败了100.00%的用户
内存消耗 :5.8 MB, 在所有 C 提交中击败了100.00%的用户

回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

本版积分规则

QQ|小黑屋|手机版|Archiver|朝阳无限好 ( 琼ICP备19005269号-1 )

GMT+8, 2020-10-1 01:54 , Processed in 0.080722 second(s), 16 queries .

快速回复 返回顶部 返回列表