二叉树定义
struct TreeNode
{
int val;
struct TreeNode *left;
struct TreeNode *right;
};
前序
主调函数
int* preorderTraversal(struct TreeNode* root, int* returnSize){
int n=size(root);
int *preorder_arry=(int*)malloc(sizeof(int)*n);
*returnSize=n;
int index=0;
//遍历
_preorderTraversal(root,preorder_arry,&index);
return preorder_arry;
}
returnSize对应二叉树节点大小;
返回节点个数
二叉树节点个数=左子树节点个数+右子树节点个数+1[if(root==NULL) return 0;]
int size(struct TreeNode*t)
{
if(t==NULL)
return 0;
else
return size(t->left)+size(t->right)+1;
}
二叉树以数组形式
void _preorderTraversal(struct TreeNode*root,int *preorder_arry,int *i)
{
if(root!=NULL)
{
preorder_arry[*i]=root->val;
(*i)++;
_preorderTraversal(root->left,preorder_arry,i);
_preorderTraversal(root->right,preorder_arry,i);
}
}
中序
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
//返回节点大小
int size(struct TreeNode*t)
{
if(t==NULL)
return 0;
else
return size(t->left)+size(t->right)+1;
}
void _inorderTraversal(struct TreeNode*root,int *inorder_arry,int *i)
{
if(root!=NULL)
{
_inorderTraversal(root->left,inorder_arry,i);
inorder_arry[*i]=root->val;
(*i)++;
_inorderTraversal(root->right,inorder_arry,i);
}
}
int* inorderTraversal(struct TreeNode* root, int* returnSize){
int n=size(root);
int *inorder_arry=(int*)malloc(sizeof(int)*n);
*returnSize=n;
//遍历
int index=0;
_inorderTraversal(root,inorder_arry,&index);
return inorder_arry;
}
后序:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int size(struct TreeNode*t)
{
if(t==NULL)
return 0;
else
return size(t->left)+size(t->right)+1;
}
void _postorderTraversal(struct TreeNode*root,int *postorder_arry,int *i)
{
if(root!=NULL)
{
_postorderTraversal(root->left,postorder_arry,i);
_postorderTraversal(root->right,postorder_arry,i);
postorder_arry[*i]=root->val;
(*i)++;
}
}
int* postorderTraversal(struct TreeNode* root, int* returnSize){
int n=size(root);
int *postorder_arry=(int*)malloc(sizeof(int)*n);
*returnSize=n;
//遍历
int index=0;
_postorderTraversal(root,postorder_arry,&index);
return postorder_arry;
}