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过子节点,而不是他本身吧
|