二叉树OJ练习(二)
1、二叉树的前序遍历
题述：给你二叉树的根节点 root ，返回它节点值的前序遍历。
示例 1：
输入：root = [1,null,2,3]
输出：[1,2,3]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
示例 4：
输入：root = [1,2]
输出：[1,2]
示例 5：
输入：root = [1,null,2]
输出：[1,2]
注意：
树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100
注意:这里的题目，要求我们将遍历结果存到数组中，将数组返回，且空指针不需要记录。那么我们可以计算出二叉树的大小，然后 动态开辟一个二叉树大小的数组。
并使用一个下标来记录数组的元素个数，最后 前序遍历二叉树 ，将结果存入数组，返回数组。
核心思想：可以先实现 TreeSize 函数 计算出二叉树的节点个数给 returnSize，并开辟好 returnSize 个 int 类型大小的数组。再调用子函数进行前序递归：如果每层函数栈帧中节点为空则结束栈帧，否则把节点放到数组里，并继续递递归
//求二叉树节点的个数 int TreeSize(struct TreeNode* root) { if (root == NULL) { return 0; } return TreeSize(root->left) + TreeSize(root->right) + 1; } //子函数用于递归 - 使用前序的方式 void _preorderTraversal(struct TreeNode* root, int* arr, int* pi) { if (root == NULL) return; //放节点 arr[(*pi)++] = root->val; _preorderTraversal(root->left, arr, pi); _preorderTraversal(root->right, arr, pi); } //Note: The returned array must be malloced, assume caller calls free(). //二叉树的前序遍厉 int* preorderTraversal(struct TreeNode* root, int* returnSize) { //*returnSize用于接收二叉树的节点个数 *returnSize = TreeSize(root); //开辟*returnSize个int类型大小的空间 int* arr = (struct TreeSize*)malloc(sizeof(int)*(*returnSize)); //因为preorderTraversal不适合递归，所以需要一个子函数；这里每一次递归都是一层函数栈帧，所以对于i来说想要保留正确的下标就要传地址 int i = 0; _preorderTraversal(root, arr, &i); return arr; }
2、二叉树的中序遍历
题述：给定一个二叉树的根节点 root ，返回它的中序遍历。
示例 1：
输入：root = [1,null,2,3]
输出：[1,2,3]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
示例 4：
输入：root = [1,2]
输出：[1,2]
示例 5：
输入：root = [1,null,2]
输出：[1,2]
注意：
树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100
核心思想：类似前序
//求二叉树节点的个数 int TreeSize(struct TreeNode* root) { if (root == NULL) { return 0; } return TreeSize(root->left) + TreeSize(root->right) + 1; } //子函数用于递归 - 使用中序的方式 void _inorderTraversal(struct TreeNode* root, int* arr, int* pi) { if(root == NULL) return; _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接收二叉树的节点个数 *returnSize = TreeSize(root); //开辟*returnSize个int类型大小的空间 int* arr = (struct TreeNode*)malloc(sizeof(int)* * returnSize); //递归调用子函数 int i = 0; _inorderTraversal(root, arr, &i); return arr; }
3、二叉树的后序遍历
题述：给定一个二叉树，返回它的后序遍历。
示例 1：
输入: [1,null,2,3]
输出: [3,2,1]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
核心思想：类似前序
//求二叉树节点的个数 int TreeSize(struct TreeNode* root) { if (root == NULL) { return 0; } return TreeSize(root->left) + TreeSize(root->right) + 1; } //子函数用于递归 - 使用后序的方式 void _postorderTraversal(struct TreeNode* root, int* arr, int* pi) { if (root == NULL) return; _postorderTraversal(root->left, arr, pi); _postorderTraversal(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接收二叉树的节点个数 *returnSize = TreeSize(root); //开辟*returnSize个int类型大小的空间 int* arr = (struct TreeNode*)malloc(sizeof(int)* * returnSize); //递归调用子函数 int i = 0; _postorderTraversal(root, arr, &i); return arr; }
