leetcode145--二叉树的后序遍历

1. 题意

求后序遍历

2. 题解

2.1 递归

class Solution {
public:
    void addPost(TreeNode *root, vector<int> &res) {
        if ( nullptr == root)
            return ;
        addPost(root->left, res);
        addPost(root->right, res);
        res.emplace_back( root->val );
    }

    vector<int> postorderTraversal(TreeNode *root) {
        vector<int> res;

        addPost(root, res);

        return res;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2.2 迭代

class Solution {
public:


    vector<int> postorderTraversal(TreeNode *root) {
        vector<int> res;
        stack<TreeNode *> s;

        TreeNode *pre = nullptr;

        while ( root || !s.empty()) {
        	// 递归遍历左子树
            if ( root ) {
                s.push(root);
                root = root->left;
                continue;
            }

			// 如果根节点没有右子树或者右子树已经访问过
            // 则将该节点的值放入答案
            // 将上一个访问完成的子树设置为当前值
            // 将当前访问的子树置为空
            // 弹出当前访问的子树(root)
            // 否则遍历右子树
            if (!s.empty()) {
                
                root = s.top();
                if (root->right == nullptr || root->right == pre ) {
                    res.emplace_back(root->val);
                    pre = root;
                    root = nullptr;
                    s.pop();
                }
                else {
                    root = root->right;
                }
            }
            
        }

        return res;
    }
};
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