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

递归

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
  public:
    vector<int> postorderTraversal(TreeNode* root) {
      std::vector<int> res;
      postorder(root, res);
      return res;
    }
  private:
    void postorder(TreeNode *root, std::vector<int> &res) {
      if (root == nullptr) {
        return ;
      }
      
      postorder(root->left, res);
      postorder(root->right, res);
      res.push_back(root->val);
    }
};

迭代：这里巧妙的利用遍历顺序和前序的关系，简单地进行一下翻转变动

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
      std::vector<int> res;
      std::stack<TreeNode *> stack_;
      
      if (root == nullptr) {
        return res;
      }
      
        //  注意这里压入的顺序，最后遍历是 根右左
      res.push_back(root->val);
      if (root->left) {
        stack_.push(root->left);
      }
      if (root->right) {
        stack_.push(root->right);
      }
      
      while (!stack_.empty()) {
        TreeNode *root = stack_.top();
        stack_.pop();
        res.push_back(root->val);
        if (root->left) {
          stack_.push(root->left);
        }
        if (root->right) {
          stack_.push(root->right);
        }
      }
      
        //  翻转序列得到 左右根
      std::reverse(res.begin(), res.end());
      
      return res;
    }
};

顺便贴上官方答案，可能不是很好理解

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        //辅助栈
        stack<TreeNode*> s; 
        TreeNode* pre = NULL; 
        while(root != NULL || !s.empty()){ 
            //每次先找到最左边的节点
            while(root != NULL){ 
                s.push(root);
                root = root->left;
            }
            //弹出栈顶
            TreeNode* node = s.top(); 
            s.pop();
            //如果该元素的右边没有或是已经访问过
            if(node->right == NULL || node->right == pre){ 
                //访问中间的节点
                res.push_back(node->val); 
                //且记录为访问过了
                pre = node; 
            }else{
                //该节点入栈
                s.push(node);
                //先访问右边
                root = node->right; 
            }
        }
        return res;
    }
};