题意：

返回二叉树的后序遍历序列

方法一：递归

确定递归终止条件：在递归的过程中，当前遍历的节点是空了，本层递归就要要结束了，所以如果当前遍历的这个节点是空，就直接return
后序遍历的遍历原则是先遍历左子树再遍历右子树，根节点，简称“左右中”

java
javascript

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型一维数组
     */
    List<Integer>res=new ArrayList<>();
    public int[] postorderTraversal (TreeNode root) {
        // write code here
        afterorder(root);
        int[]ans=new int[res.size()];
        for(int i=0;i<res.size();i++){
            ans[i]=res.get(i);
        }
        return ans;
        
    }
    void afterorder(TreeNode root){
        if(root!=null){
            afterorder(root.left);
            afterorder(root.right);
            res.add(root.val);
        }
    }
}

/*
 * function TreeNode(x) {
 *   this.val = x;
 *   this.left = null;
 *   this.right = null;
 * }
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @return int整型一维数组
 */
var res=[];
function postorderTraversal( root ) {
    // write code here
    afterorder(root);
    return res;
}
function afterorder(root){
    if(root!=null){
        afterorder(root.left);
        afterorder(root.right);
        res.push(root.val);
    }
}
module.exports = {
    postorderTraversal : postorderTraversal
};

复杂度：

时间复杂度： $O (n)$ ,每个结点只遍历一次
空间复杂度： $O (n)$ ,递归深度最深为n,每次递归地时间复杂度是常数级

方法二：迭代

利用栈来存储节点，因为前序遍历的迭代算法是“中左右”，所以我们先让根结点进栈，随后根节点出栈，如果根节点的右子树不空，右节点先进栈，如果根节点左子树不空，左节点进栈，因为栈是先进后出，所以右节点先进栈，而在后序遍历中，遍历算法是“左右中”，只需要修改前序遍历算法为“中右左”，再将得到的遍历数组逆转，即为左右中，即每次先让左节点进栈

alt

java
javascript

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型一维数组
     */
    public int[] postorderTraversal (TreeNode root) {
        // write code here
        List<Integer>res=new ArrayList<>();
        Stack<TreeNode>s=new Stack<>();
        if(root!=null)s.add(root);
        while(!s.isEmpty()){
            TreeNode x=s.pop();
            res.add(x.val);
            if(x.left!=null)s.push(x.left);
            if(x.right!=null)s.push(x.right);
            
        }
        int n=res.size();
        int[] ans=new int[n];
        for(int i=n-1;i>=0;i--){
            ans[n-1-i]=res.get(i);
        }
        return ans;
        
    }
}

/*
 * function TreeNode(x) {
 *   this.val = x;
 *   this.left = null;
 *   this.right = null;
 * }
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @return int整型一维数组
 */
function postorderTraversal( root ) {
    // write code here
    var res=[];
    var s=[];
    if(root!=null)s[0]=root;
    while(s.length>0){
        var x=s.pop();
        res.push(x.val);
        if(x.left!=null)s.push(x.left);
        if(x.right!=null)s.push(x.right);
    }
    return res.reverse();
}
module.exports = {
    postorderTraversal : postorderTraversal
};

复杂度：

时间复杂度： $O (n)$ ,一次循环
空间复杂度： $o (n)$ ,栈和数组都占用空间

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

题意：

方法一：递归

复杂度：

方法二：迭代

复杂度：