以前觉得后续遍历最难写,今天看了篇博客http://blog.csdn.net/sgbfblog/article/details/7773103,其实却是我们仔细比较后续遍历和先序遍历,其实后续遍历就是按照 根右左 的方式先序访问然后逆序就是答案了,会先序就会逆序了
leecode 的AC代码:
public class Solution {
public List<Integer> postorderTraversal(TreeNode root) { ArrayList<Integer> arry=new ArrayList<Integer>();
if(root==null) return arry;
Stack<TreeNode> s=new Stack<TreeNode>();
Stack<TreeNode> s2=new Stack<TreeNode>();
s.push(root);
while(!s.isEmpty())
{ TreeNode t=s.pop();
s2.push(t); if(t.left!=null) s.push(t.left);
if(t.right!=null) s.push(t.right); }
while(!s2.isEmpty())
{
arry.add(s2.pop().val);
}
return arry; }
}