题目
给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
示例 1：
输入：root = [1,null,2,3]
输出：[3,2,1]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
提示：
树中节点的数目在范围 [0, 100] 内
-100 <= Node.val <= 100
进阶：递归算法很简单，你可以通过迭代算法完成吗？
思路1：递归
代码1
/*** 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> ret = new LinkedList<>();public List<Integer> postorderTraversal(TreeNode root) {if(root == null) {return ret;}postorderTraversal(root.left);postorderTraversal(root.right);ret.add(root.val);return ret;}
}思路2：
代码2
/*** 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 {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> ret = new LinkedList<>();if(root == null) {return ret;}Stack<TreeNode> stack = new Stack<>();//cur表示当前需要判断的节点TreeNode cur = root;//prev表示最近一次完全结束遍历的节点TreeNode prev = null;while(cur != null || !(stack.isEmpty())) {//一路向左走到头while(cur != null) {stack.push(cur);cur = cur.left;}//左树已经全部结束cur = stack.pop();//此时cur是第二次访问，不能直接遍历，需要判断右树是否为空或者是否遍历结束if(cur.right == null || prev == cur.right) {//右树已经结束遍历，第三次访问curret.add(cur.val);//此时cur已经全部访问完毕，prev更新为当前cur节点prev = cur;cur = null;} else {stack.push(cur);//继续访问右子树cur = cur.right;}}return ret;}
}前、中、后序遍历借助栈实现，根节点啥时候能真正遍历输出？
- 前：第一次访问根节点就可以输出。
- 中：第二次访问根节点（走完左树）可以输出。
- 后：第三次访问根节点（走完子树）可以输出。
节点入栈和出栈：
- 入栈：第一次走到节点入栈。
- 出栈：当真正访问完这个节点出栈。（左、右、根）
