力扣145题:二叉树的后序遍历
给你一棵二叉树的根节点 root
,返回其节点值的 后序遍历 。
示例 1:
输入:root = [1,null,2,3] 输出:[3,2,1]
示例 2:
输入:root = [] 输出:[]
示例 3:
输入:root = [1] 输出:[1]
提示:
- 树中节点的数目在范围
[0, 100]
内 -100 <= Node.val <= 100
【方法一】递归算法
二叉树的后序遍历按照:左-右-根来进行。
针对主函数,我们需要定义一个数组a,将遍历的树中元素放在数组中;returnSize指针所指向的值初始化为0,表示结果数组的大小初始为0;调用postorder
函数,返回数组a。
针对调用函数,首先进行判断是否为空,为空的话直接进行返回,不需要进行任何操作。然后按照左-右-根来进行遍历。针对根节点处理:a[(*returnSize)++]=root->val。
具体案例分析
root = [1,null,2,3],输出:[3,2,1]。
针对主函数,开始时a[0]={},returnSize=0,调用postorder(root->left, a, returnSize),为空直接返回。进行调用postorder(root->right, a, returnSize)。由于root=2不为空,则继续进行调用postorder(root->left, a, returnSize)和postorder(root->right, a, returnSize)。
针对调用postorder(root->left, a, returnSize),此时root=3,进行调用,发现左和右均为空,则将3添加到数组a[0]中,并将 *returnSize 递增为1。然后返回到根为2时进行调用postorder(root->right, a, returnSize),为空,则将2添加到数组a[1]中,并将 *returnSize 递增为1。
此时到达最外层循环,也就是roo=1时,左为空,右已经调用完,则将1添加到数组a[2]中,并将 *returnSize 递增为1。
最终,数组 a 包含元素 [1, 2, 3],并且 *returnSize 为3。
返回数组 a。
(整个流程可以描述为,root=1->postorder(root->left, a, returnSize)为空->调用postorder(root->right, a, returnSize),此时root=2->调用postorder(root->left, a, returnSize)和postorder(root->right, a, returnSize)->首先针对postorder(root->left, a, returnSize),root=3,左右均空,将root=3加入到数组中->然后针对postorder(root->right, a, returnSize),root=2->right为空,则直接将2加入数组中->返回到最外层循环,将1加入到数组中->返回a[1,2,3]。
C语言具体代码如下:
/**
* 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().
*/
void postorder(struct TreeNode* root, int* a, int* returnSize) {
if (!root) { //树是空
return;
}
postorder(root->left, a, returnSize);
postorder(root->right, a, returnSize);
a[(*returnSize)++] = root->val;
}
int* postorderTraversal(struct TreeNode* root, int* returnSize) {
int* a = malloc(sizeof(int) * 100);
*returnSize = 0;
postorder(root, a, returnSize);
return a;
}
时间复杂度O(n);空间复杂度O(n)
【方法一】迭代算法
二叉树的后序遍历按照:左-右-根来进行。
后序遍历中,要保证左孩子和右孩子都已经被访问并且左孩子在右孩子前访问才能访问根节点。可通过辅助指针q来进行标记上一个访问的节点。
第一步创建一个栈。
第二步:定义一个stack来开辟一个栈空间,并将栈初始化,top=0。定义一个数组,用来返回最后后续遍历后的树,returnSize指针的值初始化为0,定义一个指针p来指向树的根,定义一个指针q指向空,用来标记上一个访问的节点。
第三步:当p不为空或者top不指在栈顶的时候,进判断。如果p不为空,stack->s[stack->top] = p,并将top++,进行移动,并将p指向左孩子。如果p为空的时候,p=stack->s[stack->top],然后进行判断p的右孩子是否为空或者为q。将栈中的元素给数组,并将q标记在p这个位置,然后将top--,并将p指向空。如果if语句不满足,直接将p指向右孩子。最后返回数组。
具体案例分析
root = [1,null,2,3],输出:[3,2,1]。
开始时:p=1,top=0,stack->s[0]=p=1,top++为1,将p指向左孩子为空。则,此时p=NULL。
p=NULL,执行else里面的语句。p=stack[1-1=0]=1,执行else 中if语句,不符合,则执行else中if中的else语句,p=p->right=2。则,此时p=2。
p=2,不为空,进行if (p != NULL)遇见,stack->s[1]=p=2(此时栈中1,2),top++为2,将p指向左孩子为3。则,p=3。
p=3,不为空,进行if (p != NULL)遇见,stack->s[2]=p=3(此时栈中1,2,3),top++为3,将p指向左孩子空。则,p=NULL。
p=NULL,执行else里面的语句。p=stack[3-1=2]=3,执行else 中if语句,符合,则a[0]={3},returnSize=1,q=3,top=2,p=NULL。
p=NULL,执行else里面的语句。p=stack[2-1=1]=2,执行else 中if语句,符合,则a[1]={3,2},returnSize=2,q=2,top=1,p=NULL。
p=NULL,执行else里面的语句。p=stack[1-1=0]=1,执行else 中if语句,符合,则a[2]={3,2,1},returnSize=3,q=1,top=0,p=NULL。
top=0,p=NULL,不符合while循环,跳出,返回a[2]={3,2,1}。
/**
* 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().
*/
struct stack {
struct TreeNode *s[100];
int top;
};
// 后序遍历函数
int* postorderTraversal(struct TreeNode* root, int* returnSize) {
struct stack *stack = (struct stack *)malloc(sizeof(struct stack));
stack->top = 0;
int *a = (int *)malloc(sizeof(int) * 100);
*returnSize = 0;
struct TreeNode *p = root;
struct TreeNode *q = NULL; // 用于记录上一次访问的节点
while (p != NULL || stack->top != 0) {
if (p != NULL) {
stack->s[stack->top] = p;
(stack->top)++;
p = p->left;
} else {
p = stack->s[stack->top - 1];
if (p->right == NULL || p->right == q) {
a[(*returnSize)++] = p->val;
q = p;
(stack->top)--;
p = NULL;
} else {
p = p->right;
}
}
}
return a;
}
时间复杂度O(n);空间复杂度O(n)
原文地址:https://blog.csdn.net/m0_56332819/article/details/140398297
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!