BinaryTreePostOrderTraversal [source code]
public class BinaryTreePostOrderTraversal {
static
/******************************************************************************/
public class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null)
return res;
Stack<TreeNode> s = new Stack<>();
TreeNode cur = root, prev = null, next;
while (cur != null || !s.isEmpty()) {
while (cur != null) {
s.push(cur);
cur = cur.left;
}
cur = s.peek();
//visit cur if all its rooted subtree is finished
if (cur.right == prev || cur.right == null) {
res.add(cur.val);
s.pop();
}
//go to right in next iteration unless we have just come back from right
if (cur.right == prev)
next = null;
else
next = cur.right;
prev = cur;
cur = next;
}
return res;
}
}
/******************************************************************************/
public static void main(String[] args) {
BinaryTreePostOrderTraversal.Solution tester = new BinaryTreePostOrderTraversal.Solution();
}
}
很熟悉了, 直接秒杀, 最后的速度是1ms (46%);
我之前在总结iterative DFS的时候总是区分两种写法, 一种是Stack-oriented, 一种是traversal-oriented; 但是实际上这两种做法的区分并不明显; 我觉得以后还是按照是否有explicit的push beam来区分;
有没有push beam操作的做法之间还有一个区别, 就是开始之前是否先把root给push进去; 有push beam操作的做法往往不需要这么做因为反正每一个node的操作的最开始就是先push beam, which starts from cur anyway; 但是没有push beam的做法, 往往最开始要先push root; 这样的做法虽然后面可能有从Stack领node的行为发生, 但是在对root的处理上还是与前者有很大的区别; 也许这个就是所谓的traverse-oriented?
这个是没有push beam的ver2:
public class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null)
return res;
Stack<TreeNode> s = new Stack<>();
TreeNode cur, prev = null;
s.push(root);
while (!s.isEmpty()) {
cur = s.peek();
if (prev == null || prev.left == cur || prev.right == cur) {
if (cur.left != null)
s.push(cur.left);
else if (cur.right != null) //`else` is important
s.push(cur.right);
else {
s.pop();
res.add(cur.val);
}
} else if (cur.left == prev) {
if (cur.right != null)
s.push(cur.right);
else {
s.pop();
res.add(cur.val);
}
} else { //cur.right == prev
s.pop();
res.add(cur.val);
}
prev = cur;
}
return res;
}
}
很奇妙的是, 这个版本居然稍微慢了一点: 2ms;
这个是ver3, 用Morris:
public class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null)
return res;
Stack<TreeNode> s = new Stack<>();
TreeNode dump = new TreeNode(0);
dump.left = root;
TreeNode cur = dump, prev = null;
while (cur != null) {
if (cur.left == null)
cur = cur.right;
else {
prev = cur.left;
while (prev.right != null && prev.right != cur)
prev = prev.right;
if (prev.right == null) {
prev.right = cur;
cur = cur.left;
} else {
visitReversed(cur.left, prev, res);
prev.right = null;
cur = cur.right;
}
}
}
return res;
}
public void visitReversed(TreeNode from, TreeNode to, List<Integer> ls) {
if (from == to) {
ls.add(to.val);
return;
}
visitReversed(from.right, to, ls);
ls.add(from.val);
}
}
这个的速度跟普通的Stack做法是一致的, 都是1ms; Morris的PostOrder一个比较让人遗漏的点就是这个dump的使用;
如果你研究过之前这个网页里面的trace, 你就会发现实际上打印的是时候是一条线一条线做的; 跟普通的push beam算法里面的向左的一个path作为一条线不同, 这里的一条线是向右直到走到底的一个path; dump的作用就是让我们可以用一致的办法调用visitReversed来打印最右边的这条线;
discussion最优解写的很有意思, 首先他给出了PreOrder的写法:
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode p = root;
while(!stack.isEmpty() || p != null) {
if(p != null) {
stack.push(p);
result.add(p.val); // Add before going to children
p = p.left;
} else {
TreeNode node = stack.pop();
p = node.right;
}
}
return result;
}
这个按照我们之前的定义(no push root first and also no push beam)属于traverse-oriented的做法;
他通过这个做法直接稍加修改, 得到这个做法来做到PostOrder:
public List<Integer> postorderTraversal(TreeNode root) {
LinkedList<Integer> result = new LinkedList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode p = root;
while(!stack.isEmpty() || p != null) {
if(p != null) {
stack.push(p);
result.addFirst(p.val); // Reverse the process of preorder
p = p.right; // Reverse the process of preorder
} else {
TreeNode node = stack.pop();
p = node.left; // Reverse the process of preorder
}
}
return result;
}
注意看他这里用addFirst来完成一个倒序(为了让这个操作更快, 他List的实现改成了LinkedList而不是ArrayList);
自己画一下trace就发现他这个做法其实还是挺聪明的, PreOrder和PostOrder我之前一直以为完全不同的本质, 但是这里看来, 两者也可以用非常类似的思路去理解;
这个做法总体来说我认为还是有点邪路的; 不过从某个角度上来说, PreOrder跟PostOrder确实是应该联系更加密切的; 只不过这里这个代码看似简单的修改, 其实还是很巧妙的, 暗藏玄机;
不过底下的很多评论好像对这个做法不是很买账, 不少人认为这个做法不够general(不过就是这个问题而已, 哪有什么general可言). 还有人认为:
Again, as I commented at in the most popular answer, strictly speaking, this solution for the post order is incorrect. Even though the final result is correct, imagine if there are topological dependencies among the nodes, the visiting order would be significant. Simply reversing the preorder result isn't right.
Nick's right. You're simply cheating. Because strictly speaking, you've already visited root before left and right.
这么一说, 确实是有道理的, 如果我们只是为了做一个serialization, 那么这个算法是可以的, 但是如果就是要求连encounter的顺序都是PostOrder, 那么这个算法本身确实是有点问题的;
当然也有人提出不同观点:
I wouldn't say it's necessarily cheating but more of the nature of the data structure in use (tree), and so no matter what algorithm you use, you will have to visit the root before you can get to its children. It's actually the same for topological sort as well - you will have to follow the path first to find the nodes that are not depended by any other node first
当然还是有批评的意见:
Strictly speaking, this algorithm is only for tree sequentialisation in the post order because you are not visiting the nodes in the post-order. Let's put it another way, if you are asked to do some task by traversing the tree in the post order (say, free a tree), you cannot use this algorithm.
还是比较有道理的;
这个是一个很类似我的Stack-oriented做法的算法:
public List<Integer> postorderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<TreeNode>();
List<Integer> list = new ArrayList<Integer>();
TreeNode pre = null;
TreeNode current = root;
while(current != null || !stack.isEmpty()) {
while(current != null) {
stack.push(current);
current = current.left;
}
current = stack.pop();
if(current.right != null && pre != current.right) {
stack.push(current);
current = current.right;
continue;
}
list.add(current.val);
pre = current;
current = null;
}
return list;
}
}
总体思路差不多, 不过改变了判断的敏感的case;
这个是另外一个不一样的做法:
public class Solution {
// Important, when you pop a node, ensure its children are traversed.
public List<Integer> postorderTraversal(TreeNode root) {
Stack<TreeNode> s = new Stack();
List<Integer> ans = new ArrayList<Integer>();
TreeNode cur = root;
while (cur != null || !s.empty()) {
while (!isLeaf(cur)) {
s.push(cur);
cur = cur.left;
}
if (cur != null)
ans.add(cur.val);
while (!s.empty() && cur == s.peek().right) {
cur = s.pop();
ans.add(cur.val);
}
if (s.empty())
cur = null;
else
cur = s.peek().right;
}
return ans;
}
private boolean isLeaf(TreeNode r) {
if (r == null) return true;
return r.left == null && r.right == null;
}
}
这个算法避免使用了prev指针帮助进行child判断, 最后得到的算法相应的也就有点复杂;
这个算法如果你实际上画一个trace就可以发现, 其实他判断的也是right path line, 有点类似Morris做法的PostOrder(更进一步的, 也许所有的PostOrder问题都可以转化成这个类似右倾扫描线的问题); 里面的while循环每一次触发就是processing one right path line, 这个inner loop的每一个iteration就是当前的right path line上的一个node;
当然我感觉这个作者自己设计这个算法的时候应该不是这样思考的, 而且反过来, 这样的一个思考方式好像也无法真正产出这样的一个算法; 另外, 事实上关于这个右侧扫描线的想法, 与我之前的左侧大梁的思路其实是对应的, 每一个右侧扫描线其实就是最高大梁上一个node对应的一个vertical;
而且严格来说, 这个算法对于右侧扫描线的依赖其实不如Morris严重; 这个算法首先你一看, 就跟我们之前写的那些Stack-oriented的算法很类似; 而且每一个iteration开始的时候都是push beam, 所以我觉得这个算法可能是可以用root level recursion的思路来类似理解的;
这个算法跟其他的几个算法不一样的地方, 这里你每一个subproblem用cur这个node来对应就不好理解; 你每一个subproblem最好对应的应该是s.peek(). 对于每一个node(是s.peek而不是cur): 我们先push左边大梁, 同时找到最左边的leaf, 保存在cur, 从这里开始处理, 处理完了之后, 进入到当前的s.peek(可能不同于上面讲过的那个s.peek了, 不过这个s.peek本身就应该是先处理的)的右边, 进行同样的操作(recurse): 推大梁, 然后在left leaf, 然后跳转到right leaf, 然后收右侧扫描线. 当右侧收线结束的时候, 就是当前的s.peek彻底被处理完成的时候, pop掉. 因为我们的Stack里面push的全都是左侧大梁的, 所以当我们pop掉当前的top的时候, 我们下一个得到的top其实是一个left刚刚彻底被处理完成的top, 所以我们直接进入这个top的right就行, 然后recurse;
感觉这个解释还是太imperative了, 暂时还想不到特别declarative的说法; 不过这个人对push beam算法进行这么一个简单的改写(注意, 他这里的改写实际上是比我之前的集中PostOrder的改写要小的, 因为这里没有引入prev这样的额外指针, which is just too peculiar)就可以完成PostOrder, 还是非常了不起; 感觉还是得益于他这里对于s.top的重新定义, 或者说对Stack的重新定义; 事实上, 前面的PreOrder和InOrder好像也可以用这种subproblem as s.top的思路来写; 尤其是InOrder的时候, 做的内容你想想其实是类似的: push beam, fetch top, visit, pop top, go to right, 比如假如左侧大梁从左到右是1234, 那么之前的做法就是push 4,3,2,1, fetch 1, visit 1, then fetch 2, visit 2, go to 2's right; 如果按照这里的做法, 可以理解为push 4,3,2, fetch 2's left, which is 1, visit 1, then fetch 2's right, recurse, then fetch 2 and visit; 可以看到, 我们其实可以理解为这里这个PostOrder的写法实际上是更加general的, 如果用类似的go to peek's right这样的写法, 是完全也可以改写之前的InOrder等算法的写法的; 这也是为什么这个算法改写较小的原因, 因为其实理解了这个stack-oriented approach下面的本质: Stack的top始终是当前subproblem的root;
这个是作者在代码前面说的一句话:
Your answer is short. The reverse of pre-order is skillful though may not be general. Here I attach my solution of postorderTrav without reversing pre-order. The key point is when you pop a node from stack, you ensure you have already explored its children.
我刚开始看到的时候还以为这个general是吹牛逼, 不过看来这个人是有真家伙的;
这个人还给出了另外一个需要用到prev指针的做法:
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList();
if (root == null) return ans;
Stack<TreeNode> st = new Stack();
st.push(root);
for (TreeNode p = root, prev; !st.empty();) {
prev = p;
p = st.peek();
if (p.left != null && p.left != prev && p.right != prev)
st.push(p.left);
else
if (p.right != null && p.right != prev)
st.push(p.right);
else
ans.add(st.pop().val);
}
return ans;
}
这个做法其实跟geeks4geeks上面的那个traversal-oriented的做法非常类似(注意到一开始有push root了吗). 不过他把整个逻辑简化了很多; 第一个branch判断下行过程中, 并且左边有路可走, 那么我们就push left; 否则(remind yourself, the implicit assumption afforded by else. 这个否则是什么意思? 意思就是左边已经处理完了)的话, 如果右边有路可走, 并且not been there before, 那么我们就push right; 如果左右都无路可走, 那么我们就visit当前的node; 注意他这里的else的应用, 几个branch使用else连接在一起, 所以实际上导致最后的iterate的过程的顺序是类似push beam的做法的, 这个跟geeks4geeks版本理解的时候是类似的原理;
discussion上面还有一个总结, 可以说是把上面的解法进行了一个扩展:
There is an universal idea for preorder traversal inorder traversal and postorder traversal. For each node N, we process it as follows:
push N in stack -> push left tree of N in stack -> pop left tree of N -> push right tree of N in stack -> pop right tree of N -> pop N
For preorder traversal, we visit a node when pushing it in stack. For inorder traversal, we visit a node when pushing its right child in stack. for postorder traversal, we visit a node when popping it. last_pop represents the node which is popped the last time. For the top node in stack, it has three choices, pushing its left child in stack, or pushing its right child in stack, or being popped. If last_pop != top->left, meaning that its left tree has not been pushed in stack, then we push its left child. If last_pop == top->left, we push its right child. Otherwise, we pop the top node.
void preorder_traversal_iteratively(TreeNode* root)
{
if (root == 0)
return;
stack<TreeNode*> s;
s.push(root);
cout << root->val << ' '; // visit root
TreeNode* last_pop = root;
while (!s.empty())
{
TreeNode* top = s.top();
if (top->left != 0 && top->left != last_pop && top->right != last_pop) // push_left
{
s.push(top->left);
cout << top->left->val << ' '; // visit top->left
}
else if (top->right != 0 && top->right != last_pop && (top->left == 0 || top->left == last_pop)) // push_right
{
s.push(top->right);
cout << top->right->val << ' '; // visit top->right
}
else // pop
{
s.pop();
last_pop = top;
}
}
}
void inorder_traversal_iteratively(TreeNode* root)
{
if (root == 0)
return;
stack<TreeNode*> s;
s.push(root);
TreeNode* last_pop = root;
while (!s.empty())
{
TreeNode* top = s.top();
if (top->left != 0 && top->left != last_pop && top->right != last_pop) // push_left
{
s.push(top->left);
}
else if (top->right != 0 && top->right != last_pop && (top->left == 0 || top->left == last_pop)) // push_right
{
s.push(top->right);
cout << top->val << ' '; // visit top
}
else // pop
{
s.pop();
last_pop = top;
if (top->right == 0)
cout << top->val << ' '; // visit top
}
}
}
void postorder_traversal_iteratively(TreeNode* root)
{
if (root == 0)
return;
stack<TreeNode*> s;
s.push(root);
TreeNode* last_pop = root;
while (!s.empty())
{
TreeNode* top = s.top();
if (top->left != 0 && top->left != last_pop && top->right != last_pop) // push_left
{
s.push(top->left);
}
else if (top->right != 0 && top->right != last_pop && (top->left == 0 || top->left == last_pop)) // push_right
{
s.push(top->right);
}
else // pop
{
s.pop();
last_pop = top;
cout << top->val << ' '; // visit top
}
}
}
仔细看一看的话, 这个总结其实是总结的非常好的; 注意一点的是, 这里反而好像是PreOrder显得有点复杂? 因为他这里的做法是PreOrder是在push的时候visit, 而这个模板, 是有两个cue点可以push的, 所以有两个地方要分别写对top->left和top->right的visit;
根据这个算法模板来理解, 等于说, 其实是一直有prev才是真正的最general的做法; DFS跟BFS没有太大的区别, 尽管不同于BFS的是我们有三种order的区别, 但是这三种order居然还是可以用同一个模板来处理的; 之前之所以觉得DFS的iterative这么难写, 很可能就是因为我之前看的那些算法, 尤其是PreOrder和InOrder的时候, 全都是把prev指针直接优化掉了, 所以看起来感觉千变万化, 一人一个套路; 但是实际上只要掌握了使用prev指针的通用做法, everything makes sense;
事实上, 用prev的做法本身是很有根据的:
- 有prev来保留之前的轨迹, 那么避免重复push就非常简单了; 用一个类似历史信息流算法的精神来理解的话, 本来你站在一个node的时候, 你手上几乎是很少信息的, 只有我知道我自己的left是什么, 我自己的right是什么. 而关于traversal本身的信息, 一点都没有; 这么匮乏的信息, 想要完成order的变化(traversal方式的变化), 只能靠几乎彻底的改变算法的整体设计; 而加入一个轨迹历史信息之后, 算法本身几乎可以不怎么变化, 直接改变对不同信息的判断和reaction就行了;
- cur和prev两个指针同时使用, 有一点像探路算法. 事实上, 在DFS的环境下, 用这样的算法设计, 是合理的, 因为探路, 有前后脚的概念, 才能真正帮助体现depth这个概念; 如果你手上的信息始终都是同一个level(depth)的信息, 你很难完成对depth变化操作等的有效掌握;
另外, 还是类似之前的分析, 注意这里的这个else; 这个else你可以还是用我们之前push beam的思路来理解, 实际上完成了一个推大梁的操作; 但是你也可以认为这个其实就是反映了depth first: left always overrides right, keep going deeper and deeper. 所以push beam只不过是我自己对于depth first这个概念的具象化的理解方式而已;
这个是另外一个也是通过倒置PreOrder得到的解:
class Solution {
public:
vector<int> postorderTraversal(TreeNode *root) {
stack<TreeNode*> nodeStack;
vector<int> result;
//base case
if(root==NULL)
return result;
nodeStack.push(root);
while(!nodeStack.empty())
{
TreeNode* node= nodeStack.top();
result.push_back(node->val);
nodeStack.pop();
if(node->left)
nodeStack.push(node->left);
if(node->right)
nodeStack.push(node->right);
}
reverse(result.begin(),result.end());
return result;
}
};
这个就是直接简单版本的PreOrder的写法, 稍微倒置一下就处理出来了;
这个也是一个PreOrder变形的解法:
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> results = new ArrayList<Integer>();
Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
while (!stack.isEmpty() || root != null) {
if (root != null) {
stack.push(root);
results.add(root.val);
root = root.right;
} else {
root = stack.pop().left;
}
}
Collections.reverse(results);
return results;
}
这个相对写的比较简练而且clean, 所以摆在这里;
这个是一个写法很不同的解法:
public class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<TreeNode>();
List<Integer> list = new LinkedList<Integer>();
if(root == null) return list;
stack.push(root);
TreeNode preNode = null;
TreeNode curNode = root;
while(!stack.empty()){
curNode = stack.peek();
if(curNode.left == null && curNode.right == null ||
preNode != null && (preNode == curNode.left || preNode == curNode.right)){
stack.pop();
list.add(curNode.val);
preNode = curNode;
}else{
if(curNode.right != null) stack.push(curNode.right);
if(curNode.left != null) stack.push(curNode.left);
}
}
return list;
}
}
首先, 看最后的一个branch, 看起来好像是直接PreOrder一个reverse得到的解法, 但是实际上并不是这么简单; 而看第一个branch的header, 则感觉好像是不是其实是一个InOrder? 因为preNode == curNode.left的时候居然也visit了? 但是自己实际上画一个trace看看就知道, 这个算法push的顺序跟前面所有的做法都不一样! 当你理解了他这里的push的顺序的时候, 你就会发现, 无论最后是preNode == curNode.left || preNode == curNode.right当中的任何一个, 其实都代表已经到了subtree finished的时间点, 而preNode == curNode.left代表的, 就是cur.right == null的情况(所以left处理完就可以代表cur整个都可以拉倒了);
这个做法背后的逻辑有点奇怪, 如果用推大梁的思路来理解, 这个算法其实每次是直接推两层大梁; 感觉不是很适用这个题目: 推大梁这个说法本来就是为了解决node base iteration的, 搞一个推两层大梁就没有意义了;
感觉这个算法背后的逻辑其实并没有想的那么复杂? 看到一个node, 直接两个child就倒序一push; 通过prev提供的轨迹信息来确定当前是否到了exit subtree的时间点, 到了就visit;
在一层大梁的算法当中, 我们通常通过分析每一个top对应的具有的一个invariant来分析算法的含义, 比如普通的InOrder的写法里面, 每次我们领到一个top, 我们可以保证大量左侧当前top的邻居一定已经处理完毕, which is the left child;
直接套用一层大梁的时候的这种分析并不行, 不过这里我们是否也可以找到一个关于top的invariant? 好像也没有什么特别的invariant? 因为这个算法的recursion表象实在是太强了(上面一个base case, 下面两个连着的recursive call, 连else都没有), 所以看起来deceptively simple, 反而看不出本质; 或许这个invariant就可以理解为, 也不叫invariant, 而是, when we hit branch1, which is the base case, we know for sure that the subtree rooted at top is fully processed (except for top itself), and cue post order;
总感觉这个算法应该还是有什么影藏的思想在里面, 暂时不纠结了;
除了这些, 暂时好像没看到很好的其他的解法了;
Problem Description
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?
Difficulty:Hard
Total Accepted:147.1K
Total Submissions:366.5K
Contributor: LeetCode
Related Topics
tree stack
Similar Questions
Binary Tree Inorder Traversal