leetCode解题报告之Binary Tree Postorder Traversal
source link: https://blog.csdn.net/ljphhj/article/details/21369053
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
题目：
Binary Tree Postorder Traversal
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].
Note: Recursive solution is trivial, could you do it iteratively?
分析：
初看以为是很简单的递归后序遍历二叉树的结点，之后看到要返回一个ArrayList之后，感觉如果用平常的递归遍历访问二叉树结点的话，有可能会TLE或者是StackOverFlow，之后想到要用“非递归方式”后序遍历二叉树.
解题思路：
开一个Stack，由于root结点是最后访问的结点，所以我们先将root结点push到Stack中
我们写一个while循环，while循环结束的条件是栈中没有任何结点。
当栈中有结点的时候，我们将取出栈顶结点
1、判断下它是否是叶子结点（left和right都为null）, 如果是叶子结点的话，那么不好意思，把它弹出栈，并把值add到ArrayList中，如果不是叶子结点的话，那么
2、我们判断下它的left（node.left）是否为null,如果不为null，把它的左孩子结点push到栈中来，并把它的左孩子域设为null, 然后跳过此次循环剩下的部分
3、如果它的left 为null, 把它的右孩子结点push到栈中来，并把它的右孩子域设为null，然后跳过此次循环剩下的部分！
图解：
类似的题目：
Binary Tree Preorder Traversal
Given a binary tree, return the preorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3},
1
\
2
/
3
return [1,2,3].
Note: Recursive solution is trivial, could you do it iteratively?
AC代码：
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK