java 递归及迭代 二叉树的后序遍历

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

示例:

输入: [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) {
          
   
      
    }
}

首先，我们使用递归的方式遍历

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
          
   
    // 定义一个存放结果的集合
	private List list=new ArrayList();
    
    public List<Integer> postorderTraversal(TreeNode root) {
          
   
        if(root == null) return list;
		// 后序遍历首先保存左子树
		postorderTraversal(root.left);
		// 保存右子树
		postorderTraversal(root.right);
        // 保存根节点
        list.add(root.val);
        return list;
    }
}

进阶，使用迭代的方式

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) {
          
   
        // 定义一个存放结果的集合
	    LinkedList<Integer> list=new LinkedList<Integer>();
        // 定义待处理节点的栈
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode p = root;
        while (p != null) {
          
   
        	// 后序遍历最后保存根节点，将其压栈结果
            list.push(p.val);
           
            if (p.left!= null)
            	 stack.push(p.left);
            // 将右节点赋值继续操作
             p = p.right;
             // 如果右节点为空，从栈顶获取一个最近的一个节点操作(当栈中也没有节点时，树已遍历完)
            if (p == null && stack.size() > 0) {
          
   
                p = stack.pop();
            }
        }
        return list;
    }
}

2. 常规的方式，需要同时保存根节点及右节点，但从栈中取出时直接获取右节点，逻辑稍复杂。此时需要使用一个对象记录上一个出栈加入结果集的结点，与当前结点比较，如果是当前结点的右节点，说明其左右结点均已访问，将当前结点出栈。

public List<Integer> postorderTraversal(TreeNode root) {
          
   
        // 定义一个存放结果的集合
	    List<Integer> list=new ArrayList<Integer>();
         // 定义待处理节点的栈
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode p = root;
        // 最后加入结果集的节点
        TreeNode pro=null;
         while (p != null) {
          
   
             // 因为后序先处理最左节点，父节点也处于待处理阶段，所以不管三七二十一先将节点入栈
            stack.push(p);
            p=p.left;
             // 如果左节点为空，从栈顶获取一个最近的一个节点操作(当栈中也没有节点时，树已遍历完)
            while (p == null && stack.size() > 0) {
          
   
                // 获取栈顶元素
                p = stack.peek();
                // 如果栈顶元素的右节点为空或右节点为上次结果的值，当前节点为已遍历完左右节点的父节点，直接出栈取值
                if((p=p.right)==null || p==pro){
          
   
                    pro=stack.pop();
                    list.add(pro.val);
                    p=null;
                }
            }
        }
        return list;
    }

执行结果：