题目描述

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

样例

输入: [1,null,2,3]
   1
    \
     2
    /
   3

输出: [3,2,1]

算法1

Recursive 递归 时间$O(n)$ 空间$O(n)$

后序遍历顺序是 left->right->root
从上而下递归，利用系统栈

C++ 代码

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

      left = postorderTraversal(root->left);
      for(auto &x:left) result.push_back(x);

      right = postorderTraversal(root->right);
      for(auto &x:right) result.push_back(x);

      result.push_back(root->val);

      return result;


    }
};

算法2

Iterative 迭代 $O(n)$

非递归算法需要一个栈

C++ 代码

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

        vector<int> result;
        stack<TreeNode*> s;
        if(!root)return result;

        TreeNode *current = root, *lastVisited = NULL;

        while (current != NULL || !s.empty()) {
            while (current != NULL) {
                s.push(current);
                current = current->left;
            }
            current = s.top(); 
            if (current->right == NULL || current->right == lastVisited) {
                s.pop();
                result.push_back(current->val);
                lastVisited = current;
                current = NULL;
            } else {
                current = current->right;
            }
        }
        return result;
    }
};