lc.145.二叉树的后序遍历

​

给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。

示例 1：

输入：root = [1,null,2,3] 输出：[3,2,1]

示例 2：

输入：root = [] 输出：[]

示例 3：

输入：root = [1] 输出：[1]

提示：

树中节点的数目在范围 [0, 100] 内 -100 <= Node.val <= 100

进阶：递归算法很简单，你可以通过迭代算法完成吗？

非递归解法 goto

灵感来源于这门课程 

 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

#define Node TreeNode
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        if(root==NULL ) return {};
        stack<Node*> stk;
        vector<int> ans;
        stk.push(root);
        Node *pop = nullptr;
        while(stk.size()) {
            Node *lastpush =stk.top();
            if (pop == nullptr) {
                //visite lef
                goto pushLeft;
            }else if (pop == lastpush->left ) {
                //visit left => then  visited right
                goto pushRight;
            }else {
                //visit current
                goto visitedCurrent;
            }
            pushLeft:
            if(lastpush->left) {
                pop = nullptr;
                stk.push(lastpush->left);
                continue;
            }
            pushRight:
            if(lastpush->right) {
                pop = nullptr;
                stk.push(lastpush->right);
                continue;
            }
            visitedCurrent:
            ans.push_back(lastpush->val);
            stk.pop();
            pop = lastpush;// for current
        
        }
        return ans;

    }
};

巧用 switch-case写法

 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
44
45
46
47
48
49

#define Node TreeNode
#define push_left 1
#define push_right 2

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        if(root==NULL ) return {};
        stack<Node*> stk;
        vector<int> ans;
        stk.push(root);
        Node * pop = nullptr;
        
        while(stk.size()) {
            Node* lastpush = stk.top();
            int state = 0;
            if ( pop == nullptr) {
                state = push_left;
            }else if( pop == lastpush -> left) {
                state = push_right;
            }else {
                state = 0;
            }
            switch (state) {
                case push_left: {
                    if(lastpush->left) {
                        stk.push(lastpush->left);
                        pop = nullptr;
                        break;
                    }
                }
                case push_right: {
                    if(lastpush->right) {
                        stk.push(lastpush->right);
                        pop = nullptr;
                        break;
                    }
                }
                default: {
                    ans.push_back(lastpush->val);
                    stk.pop();
                    pop = lastpush;
                }
            }
        }
        return ans;

    }
};