题目大意

给定一个二叉树，返回它的 后序 遍历。

示例:

输入: [1,null,2,3] 1 \ 2 / 3

输出: [3,2,1] 进阶: 递归算法很简单，你可以通过迭代算法完成吗？

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/binary-tree-postorder-traversal 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2.思路

构建模板

1
2
3
4
5
6
7
8
9
10
11
while( 栈非空 || p 非空)
{
if( p 非空)
{

}
else
{

}
}

填写步骤

  1. p非空一直左压
  2. 然后，如果是空的，获取栈的顶端，如果右节点也是空的或者访问了的就是p.right=pre，那么就直接访问当前的，并把p给pop出来，同时设置pre=p，标志访问，*同时设置p=null（否则下一次p会进入if判断，然后一直压）*
  3. 如果不是空的，并且没有访问，那么把p=p.right，他就会进入之前的if，一直左压

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
   vector<int> postorderTraversal(TreeNode* root) {
    stack<TreeNode*> stack1;
    vector<int> vector;
//    两个一个判断，一个向前走
    TreeNode *p=root;
    TreeNode *pre= nullptr;
    while (p||!stack1.empty()){
        if (p){
//            如果p存在就一直左压
            stack1.push(p);
            p=p->left;
        } else{
//            不存在先取top
            p=stack1.top();
            if (!p->right||p->right==pre){
//                不存在，或者是之前访问的了
                vector.push_back(p->val);
//                并设置这个也是访问的
                pre=p;
//                弹出当前的
                stack1.pop();
                p= nullptr;

            } else{
//                设置为右边的，然后他访问右边的所有左树
                p=p->right;
            }
        }
    }
    return vector;
}
};