Leetcode#145 Binary Tree Postorder Traversal

时间:2023-11-10 08:14:38

原题地址

递归写法谁都会,看看非递归写法。

对于二叉树的前序和中序遍历的非递归写法都很简单,只需要一个最普通的栈即可实现,唯独后续遍历有点麻烦,如果不借助额外变量没法记住究竟遍历了几个儿子。所以,最直接的想法就是在栈中记录到底遍历了几个儿子。

代码:

 vector<int> postorderTraversal(TreeNode *root) {
vector<int> path;
stack<pair<TreeNode *, int> > st; st.push(pair<TreeNode *, int>(root, ));
while (!st.empty()) {
pair<TreeNode *, int> top = st.top();
st.pop(); if (!top.first)
continue; if (top.second == ) {
top.second = ;
st.push(top);
st.push(pair<TreeNode *, int>(top.first->left, ));
}
else if (top.second == ) {
top.second = ;
st.push(top);
st.push(pair<TreeNode *, int>(top.first->right, ));
}
else if (top.second == ) {
path.push_back(top.first->val);
}
} return path;
}

另外还有一种技巧性比较强的写法,只使用普通的栈就可以做到。利用到了一个后续遍历的特点,即:

后续遍历序列中,父节点前面一定紧挨着他的儿子节点(如果有的话)

所以,额外保存一个prev变量代表前一个遍历的节点,就可以识别出上面的情况。如果prev节点是当前节点的儿子节点(或者当前节点没有儿子),说明当前节点的儿子节点都遍历过了,可以遍历父节点了。

如何更新维护prev呢?当一个节点输出后,将prev置为这个节点,这是因为如果prev是后续遍历序列中的前一个节点,那么这个prev节点必须是已经被输出的节点。

代码如下:

     vector<int> postorderTraversal(TreeNode *root) {
vector<int> path;
stack<TreeNode *> st;
TreeNode *prev = NULL; st.push(root);
while (!st.empty()) {
TreeNode *node = st.top(); if (!node)
st.pop();
else if ((!node->left && !node->right)
|| (prev && (node->left == prev || node->right == prev))) {
path.push_back(node->val);
st.pop();
prev = node;
}
else {
st.push(node->right);
st.push(node->left);
}
} return path;
}

也就短了几行而已。。