讨论/《二叉树》 - 二叉树的后序遍历/
《二叉树》 - 二叉树的后序遍历
共 24 个回复

迭代小思路

前序:根-左-右
后序:左-右-根

后序相当于 [根-右-左] 的逆序。

对于迭代求前序遍历可以根节点先入栈,然后右子树进栈,最后左子树进栈;
此时便可以根节点先入栈,然后左子树进栈,最后右子树进栈,最后将列表逆序即为所求。

代码

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if(root == null) return res;
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode cur = stack.pop();
            res.add(cur.val);
            if(cur.left!=null) stack.push(cur.left);
            if(cur.right!=null) stack.push(cur.right);
        }
        Collections.reverse(res);
        return res;
    }
}
8

其实仔细观察可以发现后序遍历的结果与先序遍历右子树的结果是倒序关系

7
  1. 迭代版本
//迭代版
class Solution 
{
public:
    vector<int> postorderTraversal(TreeNode* root) 
    {
        vector<int> result;
        stack<TreeNode*> s;//辅助栈
        if(root)    
            s.push(root);   //根节点首先入栈
        while(!s.empty())   //栈不是空
        {
             if(s.top()->right != root && s.top()->left != root) 栈顶非root的父亲(而为右兄弟)
                GotoLeftMostLeaf(s);//则在其右兄子树中找到最靠左的叶子
            root = s.top();
            s.pop();
            result.push_back(root->val);
        }
        return result;
    }
    void GotoLeftMostLeaf(stack<TreeNode*> &s)
    {
        while(TreeNode *x = s.top())//自顶向下反复检查栈顶节点
        {
            if(x->left)//尽可能向左,
            {
                if(x->right)//如果有右孩子,则
                    s.push(x->right);//优先入栈
                s.push(x->left);//然后转向左孩子
            }
            else //实在不得已
                s.push(x->right);//才转向右孩子
        }
        s.pop();//返回之前,弹出栈顶的空节点
    }
};
  1. 递归版本
//递归版
class Solution 
{
public:
    vector<int> postorderTraversal(TreeNode* root)
    {
        vector<int> result;
        postorder(root, result);
        return result;
    }
    void postorder(TreeNode* root, vector<int> &res)
    {
        if(!root)
            return;
        postorder(root->left, res);
        postorder(root->right, res);
        res.push_back(root->val);
    }
};
3

C++后序遍历递归写法:

    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ret;
        dfs(root, ret);     // 后序遍历递归函数,左 右 根
        return ret;
    }
    void dfs(TreeNode* root, vector<int>& ret){
        if(root == nullptr){
            return;
        }
        dfs(root->left,ret);        // 左
        dfs(root->right,ret);       // 右
        ret.push_back(root->val);   // 根
    }

C++后序遍历非递归写法:

vector<int> postorderTraversal(TreeNode* root) {
       TreeNode* p = root;
       vector<int> ret;
       stack<TreeNode*> s1;
       stack<TreeNode*> s2;
       if(p!=nullptr){
           s1.push(p);      // 头结点先压入s1中
       }
       while(!s1.empty()){
           p = s1.top();		// 每次从s1中弹出一个结点
           s1.pop();			// 弹出的结点压入s2中
           s2.push(p);

           if(p->left != nullptr){      // 先压左
               s1.push(p->left);
           }
           if(p->right != nullptr){
               s1.push(p->right);       // 再压右
           }
       }

       // 这样s1的顺序就是 根右左,s2的顺序就是左右根
       while( !s2.empty() ){
           ret.push_back(s2.top()->val);
           s2.pop();
       }
       return ret;
    }
2

java 迭代版本 在根节点后加空节点做标识

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if(root == null)
        return res;
    Deque<TreeNode> stack = new LinkedList<>();
    stack.push(root);
    while(!stack.isEmpty()){
        root = stack.pop();
        if(root != null){
            stack.push(root);
            stack.push(null);
            if(root.right != null)
                stack.push(root.right);
            if(root.left != null)
                stack.push(root.left);
        }
        else
            res.add(stack.pop().val);
    }
    return res;
}
2
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * 迭代
 * @param {TreeNode} root
 * @return {number[]}
 */
var postorderTraversal = function(root) {
    const res = [];
    const stack = [];
    let pre = null;
    while(stack.length > 0 || root !== null) {
        while(root !== null) {
            stack.push(root);
            root = root.left;
        }
        root = stack.pop();
        if (root.right === null || root.right === pre) {
            res.push(root.val);
            pre = root;
            root = null;
        } else {
            stack.push(root);
            root = root.right;
        }
    }
    return res;
};
1
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> aa={};
        if(root==NULL)
        {
            return aa;
        }
        vector<int> bb={};
        stack<TreeNode*> mystack={};
        TreeNode* Node=root;
        mystack.push(Node);
        while(!mystack.empty())
        {
            Node=mystack.top();
            mystack.pop();
            aa.push_back(Node->val);
            if(Node->left)mystack.push(Node->left);
            if(Node->right)mystack.push(Node->right);
        }
        for(auto it=aa.rbegin();it!=aa.rend();it++)
        {
            bb.push_back(*it);
        }
        return bb;
    }
};
1

解题思路

递归法。后续遍历,根节点在后。 左-右-根。
时间复杂度O(n),空间复杂度O(1)。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<Integer> result = new ArrayList<>();
    public List<Integer> postorderTraversal(TreeNode root) {
        if(root == null){
            return result;
        }
        postorderTraversal(root.left);
        postorderTraversal(root.right);
        result.add(root.val);
        return result;
    }
}
1

Morris解法(java版)

神级遍历不需要辅助栈,空间复杂度O(1),不了解Morris遍历的童鞋可以Google下,有很多讲解的文章

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list=new ArrayList<>();

        if(root==null){
            return list;
        }

        TreeNode cur=root;

        while(cur!=null){
            TreeNode most=cur.right;

            if(most==null){
                list.add(0, cur.val);
            }else{
                while(most.left!=null&&most.left!=cur){
                    most=most.left;
                }

                if(most.left==null){
                    list.add(0, cur.val);
                    most.left=cur;
                    cur=cur.right;
                    continue;
                }else{
                    most.left=null;
                }
            }

            cur=cur.left;
        }
        
        return list;
    }
}
2

Java递归

    public void travel(TreeNode t, List l1){
        if(t==null)
           return ;
        travel(t.left, l1);
        travel(t.right, l1);
        l1.add(t.val);
    }
    public List<Integer> postorderTraversal(TreeNode root) {
        List l1 = new ArrayList();
        travel(root, l1);
        return l1;
    }

Java非递归(栈)

// 因为后续遍历逆序结果等于前序遍历(先右子树)的结果
    // 所以将前序遍历(先右子树)的结果通过栈逆序输出即可
    public List<Integer> postorderTraversal(TreeNode root) {
        List l1 = new ArrayList();
        if(root==null)
           return l1;
        Stack<TreeNode> s1 = new <TreeNode>Stack();
        Stack<TreeNode> s2 = new <TreeNode>Stack();
        s1.push(root);
        while(!s1.empty()){
            TreeNode temp = s1.pop();
            s2.push(temp);
            if(temp.left!=null)
               s1.push(temp.left);
            if(temp.right!=null)
               s1.push(temp.right);
        }
        while(!s2.empty()){
            l1.add(s2.pop().val);
        }
        return l1;
    }