[LeetCode 145] Binary Tree Postorder Traversal

作者 Shilei Tian 日期 2017-02-19
[LeetCode 145] 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?

解题思路

二叉树的后序遍历,我们很容易地就写出递归版本:

class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ret;
post(root, ret);
return ret;
}
private:
void post(const TreeNode* root, vector<int>& seq) {
if (root == nullptr) {
return;
}
post(root->left, seq);
post(root->right, seq);
seq.push_back(root->val);
}
};

但是题目说,我们能不能写出一个非递归版本?依稀记得考研的时候,王道复习指南上面有一道题的答案给出了二叉树后序遍历的非递归版本,非常地复杂。看答案的时候,发现有一个非常非常巧妙的思路,值得记录下来。

我们知道,二叉树的前序遍历是根-左子树-右子树这样的遍历顺序,而后序遍历是左子树-右子树-根这样。如果我们将前序遍历稍作修改,让它按照根-右子树-左子树的顺序遍历,然后,我们再将遍历的结果逆置,不就得到了左子树-右子树-根的结果了?前序遍历的非递归版本非常简单,仅仅用到堆栈即可。所以,我们就有了下面的代码:

class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ret;
if (root == nullptr) {
return ret;
}
stack<TreeNode*> st;
st.push(root);
while (!st.empty()) {
auto node = st.top();
st.pop();
ret.push_back(node->val);
if (node->left != nullptr) {
st.push(node->left);
}
if (node->right != nullptr) {
st.push(node->right);
}
}
reverse(ret.begin(), ret.end());
return ret;
}
};

非常简洁的代码,非常奇妙的思路,值得学习!