首页 > 代码库 > Binary Tree Postorder Traversal --leetcode
Binary Tree Postorder Traversal --leetcode
原题链接:https://oj.leetcode.com/problems/binary-tree-postorder-traversal/
题目大意:后序遍历二叉树
解题思路:后序遍历二叉树的步骤:后序遍历二叉树的左子树,后序遍历二叉树的右子树,访问根结点。非递归实现时,用一个栈模拟遍历过程。由于访问完左子树后访问右子树,栈中元素要起到转向访问其右子树的作用,但是不能像先序和中序遍历那样出栈即可,因为根结点时最后访问的。那么什么时候出栈呢?我们需要一个指针pre来记录前一次访问的结点。如果pre是根结点的右子树,则说明根结点的右子树访问完了,此时根结点就可以出栈了。
class Solution{ public: vector<int> postorderTraversal(TreeNode *root) { vector<int> res; stack<TreeNode*> 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),即栈的大小树深。
后序遍历是三种遍历中最难得一种,与先序遍历和中序遍历的区别就是:需要一个指针来辅助判断是否可以访问根结点。
Binary Tree Postorder Traversal --leetcode
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。