原题
给定一个二叉树,返回它的 后序 遍历。
示例:
输入: [1,null,2,3]1\2/3输出: [3,2,1]
进阶: 递归算法很简单,你可以通过迭代算法完成吗?
class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();if(root != null){list.addAll(postorderTraversal(root.left));list.addAll(postorderTraversal(root.right));list.add(root.val);}return list;}}
class Solution {public List<Integer> postorderTraversal(TreeNode root) {LinkedList<Integer> list = new LinkedList<>();if(root == null){return list;}LinkedList<TreeNode> stack = new Stack<>();stack.push(root);while(!stack.isEmpty()){TreeNode node = stack.pop();list.addFirst(node.val);if(node.left!=null){stack.push(node.left);}if(node.right!=null){stack.push(node.right);}}return list;}}