建设部统计快报网站,计算机有哪些专业,微信网页版不显示二维码,oss 阿里云wordpress本篇博客会讲解力扣“94. 二叉树的中序遍历”的解题思路#xff0c;这是题目链接。 如何对二叉树进行中序遍历呢#xff1f;所谓中序遍历#xff0c;即先遍历左子树#xff0c;接着遍历根节点#xff0c;最后遍历右子树的一种遍历方式。具体来说#xff0c;假设有某一种“…
本篇博客会讲解力扣“94. 二叉树的中序遍历”的解题思路这是题目链接。 如何对二叉树进行中序遍历呢所谓中序遍历即先遍历左子树接着遍历根节点最后遍历右子树的一种遍历方式。具体来说假设有某一种“操作”我们称之为“中序遍历”那么这个操作就是先对左子树(root-left)做这个操作接着访问根节点的数据最后对右子树(root-right)做这个操作。
当然题目要求返回一个数组存储中序遍历访问到的数据我们需要提前知道数组需要开辟多大的空间这就可以通过一个函数TreeSize来实现。TreeSize函数负责求二叉树结点的个数方法是如果是一棵空树(root NULL)那么结点数是0否则结点数是左子树(root-left)的结点数与右子树(root-right)的结点数之和。
int TreeSize(struct TreeNode* root)
{return root NULL ? 0 : TreeSize(root-left) TreeSize(root-right) 1;
}void _inorderTraversal(struct TreeNode* root, int* a, int* pi)
{if (root NULL){return;}// 左子树 根 右子树_inorderTraversal(root-left, a, pi);a[(*pi)] root-val;_inorderTraversal(root-right, a, pi);
}int* inorderTraversal(struct TreeNode* root, int* returnSize){// 求二叉树结点个数开辟空间*returnSize TreeSize(root);int* ret (int*)malloc(sizeof(int) * *returnSize);int i 0;_inorderTraversal(root, ret, i);return ret;
}总结
大家需要牢牢掌握中序遍历的特点中序遍历是一种“操作”这种操作具体来说是先对左子树(root-left)做这种操作再访问根节点的数据最后对右子树(root-right)做这种操作。
感谢大家的阅读
