Given a binary tree, return the postorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3}
,
1
\
2
/
3
return [3,2,1]
.
后序遍历,左子树→右子树→根节点
前序遍历的非递归实现需要一个计数器,方法是需要重写一个类继承TreeNode,翁慧玉教材《数据结构:题解与拓展》P113有详细介绍,这里略。递归JAVA实现如下:
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
if (root == null)
return list;
list.addAll(postorderTraversal(root.left));
list.addAll(postorderTraversal(root.right));
list.add(root.val);
return list;
}