LeetCode：后序遍历二叉树(迭代)
想了一个下午也没想到怎么迭代遍历，认真看了以下代码以后......哦，原来是这样
大学三年，没有重视学习，现在准备考研，才知道拉下太多了。。。。
接下来就朝着自己的方向冲了，看书，健身！ 冲！！
后序遍历
若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后访问根结点。
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().
*/
/*
后遍历的流程:
一直往下走，把路口记下来，假如路口有馒头，我们是不吃的，因为要先吃最后的，中间的岔路如果有岔路，
就把右边的岔路记下来，但是因为右边没有走过，所以访问的时候也不能吃，但是左边的路因为一直往下走，
所以左边没有路了，再次回头左边那些路时，那些馒头就可以吃了。
*/
struct Stack{
struct TreeNode *node;
int p;
};
int* postorderTraversal(struct TreeNode* root, int* returnSize){
int *result = (int *)malloc(sizeof(int) * 100);
int i = 0;
struct Stack stack; //模拟栈;
int top = -1; //栈顶
int flag = 1;
while(true){
while(flag == 1 && root){
stack[++top].node = root;
stack.p = 0; //这个节点可以直接访问；
if(root->right){
stack[++top].node = root->right;
stack.p = 1; // 右节点就不能直接被访问;
}
root = root->left;
}
if(top == -1){
*returnSize = i;
return result;
}
root = stack.node; //访问栈顶元素,
flag = stack.p;
if(flag == 1)
continue; // 这时候还不能被访问的，
result = root->val;
}
}
代码源自：博客园 . 罗梁 代码源自：博客园 . 罗梁LeetCode 上有题解啊，还不错的。 永恒的蓝色梦想 发表于 2020-7-8 22:09
LeetCode 上有题解啊，还不错的。
。。。。额，我直接百度的，还不太会用leetcode，谢谢，以后就知道了，嘿嘿
页:
[1]