二叉树的后序遍历

145. 二叉树的后序遍历

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

示例:

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

输出: [3,2,1]

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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    /*
    * 后序遍历 “左右根”。需要一个栈来保存根结点，
    * 还需要一个指针来记录上一个访问的结点来判断是否访问过根结点的右子结点。
    * 当访问过树的最右叶子结点后，弹出根结点。
    */
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> s = new Stack<>();
        TreeNode lastPrintNode = null;
        
       while(root != null || ! s.isEmpty()){
           if(root != null){
               //根结点入栈
               s.push(root);
               //继续入栈根结点的左子结点
               root = root.left;
           }
           else{
               //无左子结点，将根结点复制一份
               root = s.peek();
               //查看右子结点是否为空或右子结点已经访问过
               if(root.right == null || root.right == lastPrintNode){
                   //根结点出栈
                    s.pop(); 
                   //访问根结点
                    res.add(root.val); 
                   //更新上一个访问过的结点
                    lastPrintNode = root; 
                   //取根结点的根节点访问
                    root = null;
               }else{
                   //右子结点不为空，访问右子结点
                   root = root.right;
               }
           }
       }

        return res;
    }
}

时间复杂度O(n)，空间复杂度最坏保存整个树O(n)。