1. 题目

原题链接

给定一个二叉树，返回它的 后序 遍历。
示例:
输入: [1,null,2,3]
1

2
/
3
输出: [3,2,1]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
Related Topics 栈 树
👍 393 👎 0

2. 题解

2.1 迭代(非递归)

非递归解法，使用栈
与前序遍历对比，前序遍历为 根 左 右，后序为 左 右 根，
1，若将前序遍历中每次插到链表头部，那么访问顺序 变为， 右左根，
2，若入栈时检查左右节点顺序修改 为左节点先入栈，右节点后入栈，
即变为 左右根

注意:
1.出栈时永远是按栈的后入先出顺序出栈, 即从同一个方向出入栈
2.主要改变的是每次添加结果集时的情况

    class Solution {
        public List<Integer> postorderTraversal(TreeNode root) {
            LinkedList<Integer> ans = new LinkedList<>();
            LinkedList<TreeNode> stack = new LinkedList<>();
            if (root == null) {
                return ans;
            }
            stack.offerLast(root);
            while (!stack.isEmpty()) {
                root = stack.pollLast();
                ans.addFirst(root.val);
                if (root.left != null) {
                    stack.offerLast(root.left);
                }
                if (root.right != null) {
                    stack.offerLast(root.right);
                }
            }
            return ans;
        }
    }