leetcode 链接：145. 二叉树的后序遍历

题目

给定一个二叉树，返回它的 后序 遍历。

示例：

  1. 输入: [1,null,2,3]  
  2.    1
  3.     \
  4.      2
  5.     /
  6.    3 
  8. 输出: [3,2,1]

解答 & 代码

解法一：递归

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
    void postorder(TreeNode* root, vector<int>& result)
    {
        if(root->left != nullptr)
            postorder(root->left, result);
        if(root->right != nullptr)
            postorder(root->right, result);
        result.push_back(root->val);
    }
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;

        if(root != nullptr)
            postorder(root, result);

        return result;
    }
};

执行结果：

执行结果：通过

执行用时：0 ms, 在所有 C++ 提交中击败了 100.00% 的用户
内存消耗：8.2 MB, 在所有 C++ 提交中击败了 51.31% 的用户

解法二：迭代

  • 参考前序遍历的迭代解：每访问到一个节点，先将该节点的值存到结果数组，然后将右子树节点入栈，再继续遍历左子树。
  • 前序遍历的输出顺序是 root，左，右；而后序遍历的输出顺序是 左，右，root
  • 那么修改前序遍历的迭代方式为：每访问到一个节点，先将该节点的值存到结果数组，然后将左子树节点入栈，再继续遍历右子树（和原来前序遍历对称）

  • 那么修改后的输出顺序变成 root，右，左。这和后序遍历的输出顺序正好相反，因此将最后的输出结果逆序即可

    /**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
  vector<int> postorderTraversal(TreeNode* root) {
      vector<int> result;

      stack<TreeNode*> nodeS;
      while(root != nullptr || !nodeS.empty())
      {
          while(root != nullptr)
          {
              result.push_back(root->val);    // 先访问当前节点，将当前节点的值存储到结果数组
              nodeS.push(root->left);            // 将当前节点的左子树入栈
              root = root->right;                // 访问右子树
          }

          root = nodeS.top();
          nodeS.pop();
      }

      reverse(result.begin(), result.end());
      return result;
  }
};

    执行结果： ``` 执行结果：通过

执行用时：0 ms, 在所有 C++ 提交中击败了 100.00% 的用户 内存消耗：8.2 MB, 在所有 C++ 提交中击败了 39.45% 的用户 ```