Given a binary tree, return thepostordertraversal 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?
今天又犯了个大错误,乍看这道题又轻视它了,以为不用递归也是很简单的事情。事实上,不使用递归增加了几个级数的难度啊。
不使用额外空间,我现在还是觉得不可能做到的,或许会有某些天才以后做出来吧,应该是两个思路吧:
1. 最简单应该是使用两个栈作为额外空间。感觉好浪费哦。哎呀,又感觉自己怎么那么小气啊,一点空间都不舍得,呵呵。
2. 使用额外标识,可以知道是发生了递归了,还是新进入一个node。这个好像跟回溯法差不多,但是想想还是有很大区别的。
到处上网逛了逛,好像网上的也都是这两个思路。
还是使用两个栈比较简单,下面就用递归和用两个栈实现以下吧:
非常简单的递归:
void postRecurse(TreeNode *node,vector<int> &onePath)
{
if(node == nullptr) return;
postRecurse(node->left, onePath);
postRecurse(node->right, onePath);
onePath.push_back(node->val);
}
非简单的非递归:
vector<int> postorderTraversal(TreeNode *root) {
vector<int> postPath;
postPath = postIter(root);
reverse(postPath.begin(), postPath.end());
return postPath;
}
vector<int> postIter(TreeNode *node)
{
vector<int> output;
if (!node) return output;
vector<TreeNode *> vt;
vt.push_back(node);
while (!vt.empty())
{
TreeNode *cur = vt.back();
output.push_back(cur->val);
vt.pop_back();
if (cur->left)
vt.push_back(cur->left);
if (cur->right)
vt.push_back(cur->right);
}
return output;
}
代码优雅还是最重要的,最后代码我觉得还算优雅吧,不过也参考了一下别人的代码,改进一点自己的。
最近一直在研究算法,连我的本行图形学都有荒废了,不过不要紧吧。图形学基础打的非常好了,不会那么容易丢的。先练好算法,以便研究更深奥的图形学。
虽然感觉最近功力提升了,但是还是觉得功力不到家啊,这道题琢磨了我很长时间,要努力提升!
2014-1-10更新:
上面的非递归算法,需要对后序遍历的顺序非常熟悉,然后才能逆序访问,最后反转输出结果,虽然很适合这道题,因为题目要求保存结果,但是我们也可以正常顺序非递归访问。
程序如下:
vector<int> postorderTraversal(TreeNode *root)
{
vector<int> rs;
if (!root) return rs;
stack<TreeNode *> stk;
stk.push(root);
while (!stk.empty())
{
while (stk.top()->left) stk.push(stk.top()->left);
if (stk.top()->right) stk.push(stk.top()->right);
else
{
TreeNode *t = stk.top();
stk.pop();
rs.push_back(t->val);
if (!stk.empty())
{
if (stk.top()->left == t) stk.top()->left = NULL;
else stk.top()->right = NULL;
}
}
}
return rs;
}
这样访问就会破坏了原树的结构,我们可以增加两个标志,就不会破坏原树结构了。
vector<int> postorderTraversal(TreeNode *root)
{
vector<int> rs;
if (!root) return rs;
stack<TreeNode *> stk;
stk.push(root);
bool lflag = false;
bool rflag = false;
while (!stk.empty())
{
while (!lflag && stk.top()->left) stk.push(stk.top()->left);
if (!rflag && stk.top()->right)
{
stk.push(stk.top()->right);
lflag = false;
}
else
{
TreeNode *t = stk.top();
stk.pop();
rs.push_back(t->val);
lflag = true;
if (!stk.empty() && stk.top()->right == t) rflag = true;
else rflag = false;
}
}
return rs;
}
这两个标志设计也非常巧妙的,安排不好,结果就会不正确。
非递归遍历树总结:
1 前序遍历不需要增加标志
2 中序遍历需要增加一个标志
3 后序就需要增加两个标志
难度也是一个比一个难。
//2014-2-19_1 update
vector<int> postorderTraversal(TreeNode *root)
{
vector<int> rs;
if (!root) return rs;
stack<TreeNode *> stk;
stk.push(root);
TreeNode *pre = nullptr;
while (!stk.empty())
{
if ((!pre || pre->left == stk.top() || pre->right == stk.top())
&& stk.top()->left)
{
pre = stk.top();
stk.push(stk.top()->left);
}
else if (((!stk.top()->left && pre != stk.top()->right)
|| pre == stk.top()->left) && stk.top()->right)
{
pre = stk.top();
stk.push(stk.top()->right);
}
else
{
pre = stk.top();
stk.pop();
rs.push_back(pre->val);
}
}
return rs;
}
//2014-2-19_2 update
vector<int> postorderTraversal(TreeNode *root)
{
vector<int> rs;
if (!root) return rs;
stack<TreeNode *> stk;
stk.push(root);
while (!stk.empty())
{
TreeNode *t = stk.top();
stk.pop();
rs.push_back(t->val);
if (t->left) stk.push(t->left);
if (t->right) stk.push(t->right);
}
reverse(rs.begin(), rs.end());
return rs;
}
分享到:
相关推荐
145.Binary_Tree_Postorder_Traversal二叉树的后序遍历【LeetCode单题讲解系列】
144.Binary_Tree_Preorder_Traversal二叉树的前序遍历【LeetCode单题讲解系列】
94.Binary_Tree_Inorder_Traversal二叉树的中序遍历【LeetCode单题讲解系列】
按要求输入二叉树,然后执行可输出先序 中序 后序遍历二叉树的结果。
题目地址:思路后序遍历左 - 右 - 根代码* Definition for a binary tree node.* function TreeNode(va
144-Binary Tree Preorder Traversal94-Binary Tree Inorder Traversal145-Binary Tree Postorder Traversal(后续的非递归时间不够可以先跳过,有点难)层次遍历,队列辅助,相当于广搜。102-Binary Tree Level ...
从中序与后序遍历序列构造二叉树1
只有二叉树中每个节点度为 2 或者 0 的时候,已知前序遍历序列和后序遍历序列,才能唯一地确定一颗二叉树,如果二叉树中存在度为 1 的节点时是无法唯一地确定一棵
https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/ 2 题目描述 根据一棵树的中序遍历与后序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如,给出 中序...
示例:输出: [1,3,2]进阶: 递归算法很简单,你可以通过迭代算法完成吗?* Definition for a binary tree node.* pub
主要介绍了PHP基于非递归算法实现先序、中序及后序遍历二叉树操作,结合实例形式分析了php采用非递归算法对二叉树进行先序、中序及后序遍历操作的原理与具体实现技巧,需要的朋友可以参考下
此时构建当前节点,并递归建立左右子树,在左右子树对应位置继续递归遍历进行上述步骤,直到节点为空,具体操作步骤如下:从后序遍历顺序中当前根节点的位置在 posto
public void helper(TreeNode root, int level){// 当前层没有 list,新建// 取得当前层的 list迭代pub
原创:leetcode 107. 二叉树的层次遍历 II【队列】* Definition for a binary tree node.
输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true,否则返回 false。假设输入的数组的任意两个数字都互不相同。 参考以下这颗二叉搜索树: 5 / \ 2 6 / \ 1 3 示例 1: 输入:...
实现前序遍历的序列输出// Definition for a Node.Node(int _val, vector _children) {vector pre
二叉树的前序、中序、后序、层序遍历(递归,迭代,栈,队列)1. 二叉树的前序遍历1.1 题目描述1.2 题目分析1.3 Python实现2. 二叉树的中序遍历2.1 题目描述2.2 题目分析2.3 Python实现3. 二叉树的后序遍历2.1 题目...
leetcode 树节点 二叉树中序遍历 :evergreen_tree: 给定一棵二叉树,返回其节点值的中序遍历。 Example: Input: [1,null,2,3] 1 \ 2 / 3 Output: [1,3,2] 跟进:递归解决方案是微不足道的,你能迭代吗? 中序遍历: ...
1、递归法// Definition for a Node.public Node(int _val, List<Node> _children) {List