链式存储二叉树的遍历

先序遍历，中序遍历，后序遍历以及层次遍历。

使用递归、队列。

整理自Leetcode。

说明

使用到的树结点类型为：

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

先序遍历

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

示例:

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

输出: [1,2,3]

代码:

/*求二叉树数据个数，用于动态申请空间*/
int size(struct TreeNode* root)
{
	if (!root) return 0;
	return size(root->left) + size(root->right) + 1;	// 递归求二叉树的个数
}
/*递归进行先序遍历*/
void PreOrder(struct TreeNode *root, int *ret, int *retIndex) {
	if (root == NULL) {
		return;
	}
	ret[(*retIndex)++] = root->val;			// 根
	PreOrder(root->left, ret, retIndex);	// 左
	PreOrder(root->right, ret, retIndex);	// 右
}

int* preorderTraversal(struct TreeNode* root, int* returnSize) {

    int treesize = size(root);		// 树结点数量
	int retIndex = 0;				// 数组索引
	int *ret = (int*)malloc(sizeof(int) * treesize);	// 申请空间
	memset(ret, 0, treesize);		// 置零

	PreOrder(root, ret, &retIndex);		// 先序遍历
	*returnSize = retIndex;

	return ret;

}

中序遍历

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

示例:

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

输出: [1,3,2]

代码:

int size(struct TreeNode* root)/*求二叉树数据个数*/
{
   if(!root) return 0;
   return size(root->left)+size(root->right)+1;
}

void inorder(struct TreeNode* root, int *ret, int* retIndex)/*中序遍历二叉树*/
{
	if (root == NULL) return;

	inorder(root->left, ret, retIndex);
	ret[(*retIndex)++] = root->val;
	inorder(root->right, ret, retIndex);
}

int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    
	int treesize = size(root);
    int retIndex = 0;
	int *ret = (int*)malloc(treesize * sizeof(int));
	memset(ret, 0, treesize);
	
	inorder(root, ret, &retIndex);
    *returnSize = retIndex;
     
    return ret;
}

后序遍历

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

示例:

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

输出: [3,2,1]

代码:

int size(struct TreeNode* root)/*求二叉树数据个数*/
{
   if(!root) return 0;
   return size(root->left)+size(root->right)+1;
}

void postorder(struct TreeNode* root, int *ret, int* retIndex)/*中序遍历二叉树*/
{
	if (root == NULL) return;

	postorder(root->left, ret, retIndex);
	postorder(root->right, ret, retIndex);
    ret[(*retIndex)++] = root->val;

}

int* postorderTraversal(struct TreeNode* root, int* returnSize){
    int treesize = size(root);
    int retIndex = 0;
	int *ret = (int*)malloc(treesize * sizeof(int));
	memset(ret, 0, treesize);
	
	postorder(root, ret, &retIndex);
    *returnSize = retIndex;
    return ret;
}

先序、中序、后序

显然，对于三种遍历方式，在递归实现中，唯一的不同是递归函数中ret[(*retIndex)++] = root->val语句的位置:

void order(struct TreeNode* root, int *ret, int* retIndex)
{
	if (root == NULL) return;

    //ret[(*retIndex)++] = root->val;
	postorder(root->left, ret, retIndex);
	//ret[(*retIndex)++] = root->val;
    postorder(root->right, ret, retIndex);
    //ret[(*retIndex)++] = root->val;

}

所以，对于三种遍历方式，我们可以统一写为：

/*递归求树结点的个数*/
int size(struct TreeNode *root){
    if(!root) return 0;
    return size(root->left) + size(root->right) + 1;
}
/**/
void order(struct TreeNode *root, int *ret, int *retIndex, METHOD){
    if(root==NULL) return 0;
    if(METHOD is preorder){
        
        ret[(*resIndex++)] = root->val;
        order(root->left, ret, retIndex, METHOD);
        order(root->right, ret, retIndex, METHOD);
    
    }else if(METHOD is inorder){
    
        order(root->left, ret, retIndex, METHOD);
        ret[(*resIndex++)] = root->val;
        order(root->right, ret, retIndex, METHOD);
    
    }else if(METHOD is lastorder){
    
        order(root->left, ret, retIndex, METHOD);
        order(root->right, ret, retIndex, METHOD);
        ret[(*resIndex++)] = root->val;
    
    }
}

int *orderTraversal(struct TreeNode *root, int *treeSize, METHOD){
    int treesize = size(root);
    int retIndex = 0;
    int *ret = (int*)malloc(sizeof(int)*treesize);
    memset(ret, 0, treesize);
    order(root, ret, &retIndex, METHOD);
    *returnSize = retIndex;
    return ret;
}

层次遍历

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。（即逐层地，从左到右访问所有节点）。

示例： 二叉树：[3,9,20,null,null,15,7],

返回其层次遍历结果：

[
  [3],
  [9,20],
  [15,7]
]

代码:

作者：r0vHWU5AdJ 链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal/solution/chun-cchuang-jian-dui-lie-shi-xian-er-cha-shu-de-c/ 来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */

//创建队列
//1,构建队列，实现压入和弹出函数 Push_Queue 和 Pop_Queue
//2,利用队列先进先出的特性实现二叉树的层序遍历
//3,将二叉树根 root 压入队列，并将 NULL 作为每层的区分节点也压入队列
//4,从队列中读出节点，保存当前节点的值，并且将左右支分别压入队列
//5,遇到层的区分节点则处理下一层，直到队列为空

#define     MAX_LEVEL       1000

//声明队列节点结构
struct QueueNode {
    struct TreeNode* pTreeNode;     //队列元素：二叉树节点指针
    struct TreeNodeQueue* pNext;    //队列元素：下一个节点指针
};

//声明队列结构
struct TreeNodeQueue {
    int     iNum;                   //队列元素个数
    struct QueueNode*   pHead;      //队列头指针
    struct QueueNode*   pTail;      //队列尾指针
};

//函数一：向队列中增加元素
bool Push_Queue(struct TreeNodeQueue* pQueue, struct TreeNode* pTreeNode){
    struct QueueNode*   pQueueNode = NULL;

    if(NULL == pQueue) return false;

    pQueueNode = (struct QueueNode*)malloc(sizeof(struct QueueNode));
    pQueueNode->pTreeNode = pTreeNode;
    pQueueNode->pNext = NULL;

    if(0 == pQueue->iNum)
    {
        pQueue->pHead = pQueueNode;
        pQueue->pTail = pQueueNode;
        pQueue->iNum += 1;
    }
    else
    {
        pQueue->pTail->pNext = pQueueNode;
        pQueue->pTail = pQueueNode;
        pQueue->iNum += 1;
    }

    return true;
}

//函数二：从队列中取出元素
struct TreeNode* Pop_Queue(struct TreeNodeQueue* pQueue){
    struct TreeNode*    pRet    = NULL;
    struct QueueNode*   pTmp    = NULL;

    if((NULL == pQueue) || (0 == pQueue->iNum)) return NULL;

    pRet = pQueue->pHead->pTreeNode;

    pQueue->iNum -= 1;
    if(0 == pQueue->iNum)
    {
        free(pQueue->pHead);
        pQueue->pHead = NULL;
        pQueue->pTail = NULL;
    }
    else
    {
        pTmp = pQueue->pHead->pNext;
        free(pQueue->pHead);
        pQueue->pHead = pTmp;
    }
    
    return pRet;
}

int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes){
    int         iNum        = 0;
    int         iRetSize    = 0;
    int**       pRet        = NULL;
    int*        pRetCol     = NULL;
    
    struct TreeNodeQueue  	strQueue;
    struct TreeNode* 		pTmpNode = NULL;

    //1.申请空间,并初始化
    pRet = (int**)malloc(sizeof(int*) * MAX_LEVEL);
    memset(pRet, 0x00, sizeof(int*) * MAX_LEVEL);
    pRetCol = (int*)malloc(sizeof(int) * MAX_LEVEL);
    memset(pRetCol, 0x00, sizeof(int) * MAX_LEVEL);
    memset(&strQueue, 0x00, sizeof(struct TreeNodeQueue));

    //2.特殊处理
    if(NULL == root)
    {
        *returnSize = iRetSize;
        *returnColumnSizes = pRetCol;
        return pRet;
    }

    //3.将二叉树根节点加入队列,并且加入空节点作为每层的区分节点
    Push_Queue(&strQueue, root);
    pRet[iRetSize] = (int*)malloc(sizeof(int) * strQueue.iNum);
    Push_Queue(&strQueue, NULL);

    //4.处理队列中的二叉树节点，直到队列为空
    while(strQueue.iNum != 0)
    {
        pTmpNode = Pop_Queue(&strQueue);
        if(NULL == pTmpNode)
        {
            if(0 != strQueue.iNum)
            {
                //6.当前层处理完，进入下一层
                iRetSize += 1;
                pRet[iRetSize] = (int*)malloc(sizeof(int) * strQueue.iNum);

                Push_Queue(&strQueue, NULL);
            }
        }
        else
        {
            //5.处理当前层的节点，分别将左右支压入队列
            pRet[iRetSize][pRetCol[iRetSize]] = pTmpNode->val;
            pRetCol[iRetSize] += 1;

            if(NULL != pTmpNode->left)
            {
                Push_Queue(&strQueue, pTmpNode->left);
            }
            if(NULL != pTmpNode->right)
            {
                Push_Queue(&strQueue, pTmpNode->right);
            }
        }
    }

    //7.返回
    *returnSize = iRetSize + 1;
    *returnColumnSizes = pRetCol;
    return pRet;
}