本文共 1067 字，大约阅读时间需要 3 分钟。

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

示例:

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

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

方法1：递归

class Solution {public:    void dfs(TreeNode* root, vector
   
     &re){        if(!root) return;        dfs(root->left, re);        dfs(root->right, re);        re.push_back(root->val);    }    vector
    
      postorderTraversal(TreeNode* root) {        vector
     
      re;        dfs(root, re);        return re;    }};
     
    
   

方法2：非递归方法，需要用栈来做：

（1）从根节点开始，先将根节点压入栈，然后再将其所有右子结点全部压入栈，同时取出保存这些节点值。

（2）然后分别取出栈顶节点。

（3）若栈顶节点存在左子节点，将当前指针移到其左子节点上，即跳到（1）。

这样就保证了访问顺序为根-右-左，然后reverse一下，即是左-右-根。

class Solution {public:    vector
   
     postorderTraversal(TreeNode* root) {        vector
    
     re;        stack
     
       s;        while(root || !s.empty()){            while(root){                s.push(root);                re.push_back(root->val);                root=root->right;            }            TreeNode *temp=s.top();            s.pop();            root=temp->left;        }        reverse(re.begin(), re.end());        return re;    }};
     
    
   

转载地址：http://hqabi.baihongyu.com/