145.二叉树的后序遍历
给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
示例1：
1
\
2
/
3
输入：root = [1,null,2,3]
输出：[3,2,1]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
题目来源：力扣（LeetCode）
迭代思路
能否写出：能写出，但需要参考思路
时间：30分钟
思路：
使用了一个栈来辅助遍历，模拟后序遍历的过程。首先将根节点入栈，然后从栈中取出节点并将其值添加到结果列表中。如果该节点的右子节点不为空且未被访问过，将其右子节点入栈；否则，说明该节点的右子树已经访问过，将该节点从栈中弹出，并将其值添加到结果列表中。通过不断迭代和判断，最终可以得到二叉树的后序遍历结果。
// 仅是我的思路代码，leetcode上大神更厉害 class Solution { public List<Integer> postorderTraversal(TreeNode root) { ArrayList<Integer> result = new ArrayList<>(); if (root == null) { return result; } Stack<TreeNode> stack = new Stack<>(); TreeNode temp = root; TreeNode prev = null; while (temp != null || !stack.isEmpty()) { while (temp != null) { stack.push(temp); temp = temp.left; } TreeNode top = stack.peek(); // 检查右子树是否已经访问过或为空 if (top.right == null || top.right == prev) { stack.pop(); result.add(top.val); prev = top; } else { temp = top.right; } } return result; } }
时间复杂度：O(n)
空间复杂度：O(n)
其他思路
递归：
class Solution { public List<Integer> postorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<Integer>(); postorder(root, res); return res; } public void postorder(TreeNode root, List<Integer> res) { if (root == null) { return; } postorder(root.left, res); // 递归遍历左子树 postorder(root.right, res); // 递归遍历右子树 res.add(root.val); // 访问当前节点 } }
时间复杂度：O(n)
空间复杂度：O(n)
Morris 后序遍历
