题目:给定一个二叉树的根节点 root ,返回 它的 中序 遍历 。
示例 1: 输入:root = [1, null, 2, 3] 输出:[1, 3, 2]
示例 2: 输入:root = [] 输出:[]
示例 3: 输入:root = [1] 输出:[1]
提示: 树中节点数目在范围[0, 100] 内
思路:二叉树的中序遍历,化为子问题先遍历当前根的左子树,再打印当前根的值,最后遍历当前根的右子树;
void Inorder(struct TreeNode* root, int* a, int* pos)
{
if (root == NULL)
return;
//先递归当前根的左子树;再将当前根的 val 存放到数组中;最后递归当前根的右子树
Inorder(root->left, a, pos);
a[(*pos)++] = root->val;
Inorder(root->right, a, pos);
}
int* inorderTraversal(struct TreeNode* root, int* returnSize)
{
//开辟一个返回中序遍历的数组,pos记录数组的长度
int* ret = (int*)malloc(sizeof(int) * 100);
int pos = 0;
//进入中序遍历
Inorder(root, ret, &pos);
*returnSize = pos;
return ret;
}
题目:给你一棵二叉树的根节点 root ,返回其节点值的 后序遍历 。
示例 1: 输入:root = [1, null, 2, 3] 输出:[3, 2, 1]
示例 2: 输入:root = [] 输出:[]
示例 3: 输入:root = [1] 输出:[1]
提示: 树中节点的数目在范围[0, 100] 内
思路:二叉树的后序遍历,化为子问题先遍历当前根的左子树,再遍历当前根的右子树,最后打印当前根的值;
void Postorder(struct TreeNode* root, int* a, int* pos)
{
if (root == NULL)
return;
//先递归当前根的左子树;再递归当前根的右子树;最后将当前根的 val 存放到数组中
Postorder(root->left, a, pos);
Postorder(root->right, a, pos);
a[(*pos)++] = root->val;
}
int* postorderTraversal(struct TreeNode* root, int* returnSize)
{
//开辟返回的数组
int* ret = (int*)malloc(sizeof(int) * 100);
int pos = 0;
//进入后序遍历
Postorder(root, ret, &pos);
*returnSize = pos;
return ret;
}