【OJ - 二叉树】二叉树的前、中、后序遍历

文章目录

这三道OJ题解题思路类似，你只要会其中一道，其它两道也就会了

一、二叉树的前序遍历

题目难度：简单

1.1 题目描述

给你二叉树的根节点

root

，返回它节点值的 前序 遍历。

LeetCode链接：144. 二叉树的前序遍历 - 力扣（LeetCode）

1.2 解题思路

递归遍历

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */// 写一个函数来计算树的节点个数intTreeSize(struct TreeNode* root){if(root ==NULL){return0;}return1+TreeSize(root->left)+TreeSize(root->right);}// 写一个子函数来前序遍历void_preorderTraversal(struct TreeNode* root,int* arr,int* pi){// 先判断当前节点是否为空if(root ==NULL){return;}// 前序遍历二叉树的节点值依次放入数组arr中
    arr[(*pi)]= root->val;(*pi)++;// 数组下标+1_preorderTraversal(root->left, arr, pi);_preorderTraversal(root->right, arr, pi);}/**
 * Note: The returned array must be malloced, assume caller calls free().
 * returnSize：返回的数组的大小
 */int*preorderTraversal(struct TreeNode* root,int* returnSize){// 根据题目要求，需要动态开辟一个数组，存放树的节点值（的前序遍历）*returnSize =TreeSize(root);// 计算树的节点个数int* arr =(int*)malloc(sizeof(int)*(*returnSize));// 从根节点(0)开始，前序遍历二叉树int i =0;_preorderTraversal(root, arr,&i);// 返回数组return arr;}

二、二叉树的中序遍历

题目难度：简单

2.1 题目描述

给定一个二叉树的根节点

root

，返回它的 中序 遍历。

LeetCode链接：94. 二叉树的中序遍历 - 力扣（LeetCode）

2.2 解题思路

递归遍历

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */// （前序遍历）计算二叉树节点个数intTreeSize(struct TreeNode* root){if(root ==NULL){return0;}return1+TreeSize(root->left)+TreeSize(root->right);}// 中序遍历二叉树各节点的值，依次放到数组arr中void_inorderTraversal(struct TreeNode* root,int*arr,int* pi){if(root){_inorderTraversal(root->left, arr, pi);
        arr[(*pi)++]= root->val;_inorderTraversal(root->right, arr, pi);}}/**
 * Note: The returned array must be malloced, assume caller calls free().
 */int*inorderTraversal(struct TreeNode* root,int* returnSize){// 动态开辟一个数组*returnSize =TreeSize(root);// 计算二叉树节点个数，即数组长度int* arr =(int*)malloc(sizeof(int)*(*returnSize));if(arr ==NULL){perror("malloc");exit(-1);}// 中序遍历二叉树各节点的值，依次放到数组中int i =0;_inorderTraversal(root, arr,&i);// 返回数组return arr;}

三、二叉树的后序遍历

题目难度：简单

3.1 题目描述

给你一棵二叉树的根节点

root

，返回其节点值的 后序遍历 。

LeetCode链接：145. 二叉树的后序遍历 - 力扣（LeetCode）

3.2 解题思路

递归遍历

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */// （前序遍历）计算二叉树节点个数intTreeSize(struct TreeNode* root){if(root ==NULL){return0;}return1+TreeSize(root->left)+TreeSize(root->right);}// 后序遍历二叉树各节点的值，依次放到数组arr中void_inorderTraversal(struct TreeNode* root,int*arr,int* pi){if(root){_inorderTraversal(root->left, arr, pi);_inorderTraversal(root->right, arr, pi);
        arr[(*pi)++]= root->val;}}/**
 * Note: The returned array must be malloced, assume caller calls free().
 */int*postorderTraversal(struct TreeNode* root,int* returnSize){// 动态开辟一个数组*returnSize =TreeSize(root);// 计算二叉树节点个数，即数组长度int* arr =(int*)malloc(sizeof(int)*(*returnSize));if(arr ==NULL){perror("malloc");exit(-1);}// 后序遍历二叉树各节点的值，依次放到数组中int i =0;_inorderTraversal(root, arr,&i);// 返回数组return arr;}