Leetcode: Binary Tree Postorder Traversal（二叉树后序遍历）
Leetcode: Binary Tree Postorder Traversal（二叉树后序遍历）
卡尔曼和玻尔兹曼谁曼
发布于 2019-01-22 15:28:36
发布于 2019-01-22 15:28:36
题目： Given a binary tree, return the postorder traversal of its nodes’ values.
For example: Given binary tree {1,#,2,3},
1
\
2
/
3return [3,2,1].
Note: Recursive solution is trivial, could you do it iteratively?
递归解法（C++版本）：
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution
{
private:
vector<int> result;
public:
vector<int> postorderTraversal(TreeNode *root)
{
if (root)
{
postorderTraversal(root->left);
postorderTraversal(root->right);
result.push_back(root->val);
}
return result;
}
};二叉树非递归后序遍历思路： 二叉树非递归后续遍历是三种遍历中最难的，因为后续遍历最后访问根节点，操作中不好回溯到根节点，而前序遍历和中序遍历中，每次循环遍历中都是从根节点开始回溯很容易。 网上好些代码都是使用一个栈Stack进行操作的，代码不易懂，读起来很吃力。 其实，可以使用两个Stack来进行二叉树非递归后续遍历。先访问根节点，入栈（A栈），记住根节点，出栈进入另外一个栈（B栈），然后该根节点左右子树入栈（A栈）。最后输出B栈的结果就OK了。
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution
{
public:
vector<int> postorderTraversal(TreeNode *root)
{
vector<int> result;
if (!root) return result;
stack<TreeNode*> outputStack;
stack<TreeNode*> middleStack;
middleStack.push(root);
TreeNode *node = nullptr;
while (!middleStack.empty())
{
node = middleStack.top();
middleStack.pop();
outputStack.push(node);
if (node->left)
{
middleStack.push(node->left);
}
if (node->right)
{
middleStack.push(node->right);
}
}
while (!outputStack.empty())
{
result.push_back(outputStack.top()->val);
outputStack.pop();
}
return result;
}
};C#非递归参考代码：
/**
* Definition for binary tree
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int x) { val = x; }
* }
*/
public class Solution
{
public IList<int> PostorderTraversal(TreeNode root)
{
IList<int> result = new List<int>();
if (root == null) return result;
Stack<TreeNode> outputStack = new Stack<TreeNode>();
Stack<TreeNode> middleStack = new Stack<TreeNode>();
middleStack.Push(root);
TreeNode node = null;
while (middleStack.Count != 0)
{
node = middleStack.Pop();
outputStack.Push(node);
if (node.left != null) middleStack.Push(node.left);
if (node.right != null) middleStack.Push(node.right);
}
while (outputStack.Count != 0)
{
result.Add(outputStack.Pop().val);
}
return result;
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2015年04月02日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读