【LeetCode】145. 二叉树的后序遍历（Java）

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

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

解法一

递归

/** * 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> res = new ArrayList<>(); public List<Integer> postorderTraversal(TreeNode root) { //递归 if (root == null) return res; //后序遍历 postorderTraversal(root.left); postorderTraversal(root.right); res.add(root.val); return res; } }

解法二

迭代

class Solution { public List<Integer> postorderTraversal(TreeNode root) { //迭代 List<Integer> res = new ArrayList<>(); //栈 Deque<TreeNode> stack = new ArrayDeque<>(); TreeNode cur = root; //cur代表遍历时当前的节点 TreeNode last = null; //记录右子节点（代表已经访问了右子节点） while (!stack.isEmpty() || cur != null) { //一直走到最左叶子节点的左节点（即null） while (cur != null) { stack.push(cur); cur = cur.left; } //获取栈顶，不删除 cur = stack.peek(); //如果当前节点的右节点为空或者访问过了 if (cur.right == null || cur.right == last) { res.add(cur.val); //因为上面只是peek，所以需要删除栈顶 stack.pop(); //记录下此时的右子节点（代表已经访问过了） last = cur; //清空，下次循环从栈中获取节点 cur = null; } else { //右子节点存在，并且没访问过，进入右子节点 cur = cur.right; } } return res; } }

思路是看long_wotu题解评论区的Alex Zheng的题解。

一道比一道难，前中后，迭代方式就后序最难理解了。