Given a binary tree, return the postorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3},
return [3,2,1].
Note: Recursive solution is trivial, could you do it iteratively?
题意：后序遍历，即左右中。
思路：
1、分治递归遍历左右中。
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
helper(root, res);
return res;
}
private void helper(TreeNode node, List<Integer> res) {
if (node == null) {
return;
}
helper(node.left, res);
helper(node.right, res);
res.add(node.val);
}
2、修改前序遍历为中右左，再把list翻转就变成了左右中。
public List<Integer> postorderTraversal1(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode cur = stack.pop();
res.add(cur.val);
if (cur.left != null) {
stack.push(cur.left);
}
if (cur.right != null) {
stack.push(cur.right);
}
}
Collections.reverse(res);
return res;
}