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翻轉(zhuǎn)就變成了左右中稠通。
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;
}