LeetCode--binary-tree-postorder-traversal

2018-01-06 11:01:25来源:网络收集作者:咖啡不加糖人点击

分享

题目描述



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?


题目大意:后序遍历二叉树
解题思路:后序遍历二叉树的步骤:后序遍历二叉树的左子树,后序遍历二叉树的右子树,访问根结点。非递归实现时,用一个栈模拟遍历过程。由于访问完左子树后访问右子树,栈中元素要起到转向访问其右子树的作用,但是不能像先序和中序遍历那样出栈即可,因为根结点时最后访问的。那么什么时候出栈呢?我们需要一个指针pre来记录前一次访问的结点。如果pre是根结点的右子树,则说明根结点的右子树访问完了,此时根结点就可以出栈了。


/**
* 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 postorderTraversal(TreeNode *root) {
vector res;
stack s;
TreeNode* pre=NULL;
while(root||!s.empty())
{
if(root)
{
s.push(root);
root=root->left;
}
else if(s.top()->right!=pre)
{
root=s.top()->right;
pre=NULL;
}
else
{
res.push_back(s.top()->val);
pre=s.top();
s.pop();
}
}
return res;
}
};
时间复杂度:O(N),每个结点访问仅一次。  空间复杂度:O(lgN),即栈的大小树深。
后序遍历是三种遍历中最难得一种,与先序遍历和中序遍历的区别就是:需要一个指针来辅助判断是否可以访问根结点。

最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台