后序遍历二叉树

两种方法：

1. 常规方案——正规的后序遍历，关键在于设置空指针
2. 利用规律——按照根->右->左的方式访问后，再reverse结果

常规方法

//
// Created by jt on 2020/8/8.
//
#include 
#include 
#include 
using namespace std;
/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 * };
 */
class Solution {
public:
    /**
     *
     * @param root TreeNode类
     * @return int整型vector
     */
    vector postorderTraversal(TreeNode *root) {
        // write code here
        // 正规解法
        // 1.辅助栈 2.关键在于设空指针
        vector result;
        if (!root) return result;
        stack record;
        record.push(root);
        while (!record.empty()) {
            TreeNode *current = record.top();
            if (!current->left && !current->right) {
                result.push_back(current->val);
                record.pop();
            } else {
                // 因为访问顺序是先左后右，因此先推入右再推入左
                if (current->right) {
                    record.push(current->right);
                    current->right = nullptr;            // 设置成空指针，防止再次访问
                }
                if (current->left) {
                    record.push(current->left);
                    current->left = nullptr;
                }
            }
        }
        return result;
    }
};

利用规律

//
// Created by jt on 2020/8/8.
//
#include 
#include 
#include 
using namespace std;
/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 * };
 */
class Solution {
public:
    /**
     *
     * @param root TreeNode类
     * @return int整型vector
     */
    vector postorderTraversal(TreeNode *root) {
        // write code here
        // 非正规解法
        // 1.辅助栈 2.前序的根->左->右变成根->右->左再reverse
        vector result;
        if (!root) return result;
        stack record;
        record.push(root);
        while (!record.empty()) {
            TreeNode *current = record.top();
            record.pop();
            result.push_back(current->val);
            if (current->left) record.push(current->left);
            if (current->right) record.push(current->right);
        }
        reverse(result.begin(), result.end());
        return result;
    }
};