leetcode145--二叉树的后序遍历-Toy模板网

这篇具有很好参考价值的文章主要介绍了leetcode145--二叉树的后序遍历。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1. 题意

求后序遍历文章来源地址https://www.toymoban.com/news/detail-858922.html

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

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