题解 | #二叉树的后序遍历#

方法一：递归

二叉树的后序遍历顺序：左节点->右节点->根节点。先依次进入左右子树进行递归，再保留根节点的值。

时间复杂度：o(n)。需要遍历二叉树的所有节点，需要o(n)。

空间复杂度：o(n)。需要开辟空间保存中序遍历的节点值。

class Solution {
public:
    void post_search(TreeNode* root, vector<int>& post_tree) {
	  	//节点为空时返回
        if(root == nullptr)
            return;
        //递归遍历左子树
        post_search(root->left, post_tree);
	  	//递归遍历右子树
        post_search(root->right, post_tree);
	  	//保存根节点的值
        post_tree.push_back(root->val);
    }
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> post_tree;
        post_search(root, post_tree);
        return post_tree;
    }
};

方法二：栈（非递归）

具体做法：

• step 1：开辟一个辅助栈，用于记录要访问的子节点，开辟一个前序指针pre。
• step 2：从根节点开始，每次优先进入每棵的子树的最左边一个节点，我们将其不断加入栈中，用来保存父问题。
• step 3：弹出一个栈元素，看成该子树的根，判断这个根的右边有没有节点或是有没有被访问过，如果没有右节点或是被访问过了，可以访问这个根，并将前序节点标记为这个根。
• step 4：如果没有被访问，那这个根必须入栈，进入右子树继续访问，只有右子树结束了回到这里才能继续访问根。

时间复杂度：o(n)。

空间复杂度：o(n)。

class Solution {
  public:
    vector<int> post;
    vector<int> postorderTraversal(TreeNode* root) {
        //特殊情况处理
        if (root == nullptr)
            return post;

        stack<TreeNode*> temp;
        TreeNode* pre = NULL;

        while (!temp.empty() || root != nullptr) {
            //找到最左边的结点
            while (root != nullptr) {
                temp.push(root);
                root = root->left;
            }

            TreeNode* node = temp.top();
            //当该元素右边没有结点，或者是右节点已经被访问过
            if (node->right == nullptr || node->right == pre) {
                post.push_back(node->val);
                temp.pop();
                pre = node;
            } else
                root = node->right;
        }

        return post;
    }
};