概述
一、二叉树的前序遍历(根节点,左子树,右子树)
1.1 题目描述
给定一个二叉树,返回它的 前序 遍历。
示例:
输入: [1,null,2,3]
1
2
/
3
输出: [1,2,3]
1.2 代码实现
int treeSize(struct TreeNode* root)//计算所遍历二叉树节点的个数
{
if(root == NULL)
return 0;
else
return treeSize(root->left)+treeSize(root->right)+1;
}
//为方便递归构造的子函数
void _preorderTraversal(struct TreeNode* root,int* preorder,int* pindex)
{
if(root == NULL)
return;
preorder[*pindex] = root->val;//访问根节点
++(*pindex);
_preorderTraversal(root->left,preorder,pindex);//访问左子树
_preorderTraversal(root->right,preorder,pindex);//访问右子树
}
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
*returnSize = treeSize(root);
int* preorder = (int*)malloc(*returnSize * sizeof(int));
int index = 0;
_preorderTraversal(root,preorder,&index);
return preorder;
}
二、二叉树的中序遍历(左子树,根节点,右子树)
2.1 题目描述
给定一个二叉树,返回它的中序 遍历。
示例:
输入: [1,null,2,3]
1
2
/
3
输出: [1,3,2]
2.2 代码实现
int treeSize(struct TreeNode* root)
{
if(root == NULL)
return 0;
else
return treeSize(root->left)+treeSize(root->right)+1;
}
void _postorderTraversal(struct TreeNode* root,int* postorder,int* pindex)
{
if(root == NULL)
return;
_postorderTraversal(root->left,postorder,pindex);
postorder[*pindex] = root->val;
++(*pindex);
_postorderTraversal(root->right,postorder,pindex);
}
int* postorderTraversal(struct TreeNode* root, int* returnSize) {
*returnSize = treeSize(root);
int* postorder = (int*)malloc(*returnSize*sizeof(int));
int index = 0;
_postorderTraversal(root,postorder,&index);
return postorder;
}
三、二叉树的后序遍历(左子树,右子树,根节点)
3.1 题目描述
给定一个二叉树,返回它的中序 遍历。
示例:
输入: [1,null,2,3]
1
2
/
3
输出: [3,2,1]
3.2 代码实现
int treeSize(struct TreeNode* root)
{
if(root == NULL)
return 0;
else
return treeSize(root->left)+treeSize(root->right)+1;
}
void _postorderTraversal(struct TreeNode* root,int* postorder,int* pindex)
{
if(root == NULL)
return;
_postorderTraversal(root->left,postorder,pindex);
_postorderTraversal(root->right,postorder,pindex);
postorder[*pindex] = root->val;
++(*pindex);
}
int* postorderTraversal(struct TreeNode* root, int* returnSize) {
*returnSize = treeSize(root);
int* postorder = (int*)malloc(*returnSize*sizeof(int));
int index = 0;
_postorderTraversal(root,postorder,&index);
return postorder;
}
最后
以上就是忧心小天鹅为你收集整理的【LeetCode】—— 二叉树的遍历的全部内容,希望文章能够帮你解决【LeetCode】—— 二叉树的遍历所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复