【数据结构---25】链式结构二叉树的前、中、后序遍历

前序遍历:

题目描述：

给定一个二叉树，返回它的前序遍历

示例:

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

1 \ 2 / 3

输出: [1,2,3]

/** * 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(). */

思路分析:

1.首先使用递归的方法求出节点的个数,跳出条件是当root==NULL的时候,0个 2.对形参的指针修改相当于修改外部实参 3.把遍历好的元素存放到数组里,最后返回数组

代码实现:

typedef struct TreeNode Node; //这里的size必须传指针,不然size作为临时变量,作用域和生命周期只有函数段 void PreOrder(Node* Root,int * Res,int * size) { if(Root!=NULL) { Res[*size]=Root->val; (*size)++; PreOrder(Root->left,Res,size); PreOrder(Root->right,Res,size); } } int Getsize(Node* Root) { if(Root==NULL) { return 0; } return Getsize(Root->left)+Getsize(Root->right)+1; } //对形参的指针修改,相当于修改外部实参 int* preorderTraversal(struct TreeNode* root, int* returnSize) { *returnSize=Getsize(root); int* Res=(int*)malloc(sizeof(int)* (*returnSize)); if(Res==NULL) { assert(0); } int size=0; PreOrder(root,Res,&size); return Res; }

对于中序和后序的处理:只需要修改遍历语句的顺序即可

中序遍历:

题目描述:

给定一个二叉树，返回它的中序遍历

示例:

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

输出: [1,3,2]

代码实现:

void inOrder(Node* Root,int * Res,int * size) { if(Root!=NULL) { inOrder(Root->left,Res,size); Res[*size]=Root->val; (*size)++; inOrder(Root->right,Res,size); } }

后序遍历:

题目描述:

给定一个二叉树，返回它的 后序遍历

示例:

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

输出: [3,2,1]

代码实现:

void PostOrder(Node* Root,int * Res,int * size) { if(Root!=NULL) { PostOrder(Root->left,Res,size); PostOrder(Root->right,Res,size); Res[*size]=Root->val; (*size)++; } }