s********u
发帖数: 1109 | |
n****e
发帖数: 678 | 2 这个binary tree iterative traversal 的codes 貌似不对，再仔细看看 |
s********u
发帖数: 1109 | 3 我改了改，发现还是不行，是我想错了。
主要是不用别的数据结构，或者不改树的话，没法确定一个节点是否已经“处理”过
【在 n****e 的大作中提到】
: 这个binary tree iterative traversal 的codes 貌似不对，再仔细看看
|
n****e
发帖数: 678 | 4 你太客气了，不用抱歉哈 :)
这个codes还是不对，你是想写post-order iterative traversal吧
你试着run这个test：
1
2 3
4 5 6 7
这个condition： if(!node->right && !node->left) 对node 2， node 3 不work
【在 s********u 的大作中提到】
: 我改了改，发现还是不行，是我想错了。
: 主要是不用别的数据结构，或者不改树的话，没法确定一个节点是否已经“处理”过
|
b*******e
发帖数: 123 | 5 post-order那个，不能用pre-order的code，反着推左右分支，然后结果倒序么？ |
n****e
发帖数: 678 | 6 in-order 和 post-order 需要对节点进行标记。 当是第二次访问的时候，再输出。
【在 b*******e 的大作中提到】
: post-order那个，不能用pre-order的code，反着推左右分支，然后结果倒序么？
|
s********u
发帖数: 1109 | 7 嗯我自己推了一下就发现问题在哪了。就是说还是需要标记或者"封装"的。
比如建一个tree的类，然后pop出来如果发现是tree，就分成节点和tree；如果是节点
，就直接读取。最后读到的都是节点。
但这样的话，需要再建一个base class是用tree或者节点作为构造的参数的。
【在 n****e 的大作中提到】
: 你太客气了，不用抱歉哈 :)
: 这个codes还是不对，你是想写post-order iterative traversal吧
: 你试着run这个test：
: 1
: 2 3
: 4 5 6 7
: 这个condition： if(!node->right && !node->left) 对node 2， node 3 不work
|
n****e
发帖数: 678 | 8 恩，是的，每个node需要一个变量来标记，是否已经访问过。当第二次访问的时候，再
输出
【在 s********u 的大作中提到】
: 我改了改，发现还是不行，是我想错了。
: 主要是不用别的数据结构，或者不改树的话，没法确定一个节点是否已经“处理”过
|
s********u
发帖数: 1109 | 9 这个变量需要标记的是是否push过子节点，而不是他本身吧
【在 n****e 的大作中提到】
: 恩，是的，每个node需要一个变量来标记，是否已经访问过。当第二次访问的时候，再
: 输出
|
b*******e
发帖数: 123 | 10 今天刚做的。
vector preorderTraversal(TreeNode *root) {
if(root == nullptr) return {};
vector res;
stack stack;
stack.push(root);
while(!stack.empty()){
auto top = stack.top(); stack.pop();
res.push_back(top->val);
if(top->right!=nullptr) stack.push(top->right);
if(top->left !=nullptr) stack.push(top->left);
}
return res;
}
vector postorderTraversal(TreeNode *root) {
if(root==nullptr) return {};
stack stack;
stack.push(root);
vector res;
while(!stack.empty()){
auto x = stack.top(); stack.pop();
res.push_back(x->val);
if(x->left != nullptr) stack.push(x->left);
if(x->right != nullptr) stack.push(x->right);
}
reverse(res.begin(),res.end());
return res;
} |
n****e
发帖数: 678 | 11 恩，对的
【在 s********u 的大作中提到】
: 这个变量需要标记的是是否push过子节点，而不是他本身吧
|
