LeetCode：后序遍历二叉树(迭代)

慵懒的勤快孩儿

想了一个下午也没想到怎么迭代遍历，认真看了以下代码以后......哦，原来是这样

大学三年，没有重视学习，现在准备考研，才知道拉下太多了。。。。

接下来就朝着自己的方向冲了，看书，健身！ 冲！！


后序遍历
若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后访问根结点。

C语言实现：

1. /**
   
2. * Definition for a binary tree node.
   
3. * struct TreeNode {
   
4. *     int val;
   
5. *     struct TreeNode *left;
   
6. *     struct TreeNode *right;
   
7. * };
   
8. */
   
9. 
   
10. 
    
11. /**
    
12. * Note: The returned array must be malloced, assume caller calls free().
    
13. */
    
14. 
    
15. 
    
16. /*
    
17. 后遍历的流程:
    
18. 一直往下走，把路口记下来，假如路口有馒头，我们是不吃的，因为要先吃最后的，中间的岔路如果有岔路，
    
19. 就把右边的岔路记下来，但是因为右边没有走过，所以访问的时候也不能吃，但是左边的路因为一直往下走，
    
20. 所以左边没有路了，再次回头左边那些路时，那些馒头就可以吃了。
    
21. */
    
22. 
    
23. struct Stack{
    
24.     struct TreeNode *node;
    
25.     int p;
    
26. };
    
27. 
    
28. int* postorderTraversal(struct TreeNode* root, int* returnSize){
    
29.    
    
30.     int *result = (int *)malloc(sizeof(int) * 100);
    
31.     int i = 0;
    
32.     struct Stack stack[100]; //模拟栈;
    
33.    
    
34.     int top = -1; //栈顶
    
35.     int flag = 1;
    
36.     while(true){
    
37.         while(flag == 1 && root){
    
38.             stack[++top].node = root;
    
39.             stack[top].p = 0; //这个节点可以直接访问；
    
40.             if(root->right){
    
41.             stack[++top].node = root->right;
    
42.             stack[top].p = 1; // 右节点就不能直接被访问;
    
43.             }
    
44.             root = root->left;
    
45.         }
    
46.         if(top == -1){
    
47.             *returnSize = i;
    
48.             return result;
    
49.         }
    
50.         root = stack[top].node; //访问栈顶元素,
    
51.         flag = stack[top--].p;
    
52.         if(flag == 1)
    
53.             continue; // 这时候还不能被访问的，
    
54.         result[i++] = root->val;     
    
55.     }
    
56. }

复制代码

代码源自：博客园 . 罗梁

永恒的蓝色梦想

代码源自：博客园 . 罗梁

LeetCode 上有题解啊，还不错的。

慵懒的勤快孩儿

永恒的蓝色梦想 发表于 2020-7-8 22:09
LeetCode 上有题解啊，还不错的。

。。。。额，我直接百度的，还不太会用leetcode，谢谢，以后就知道了，嘿嘿