h**o
发帖数: 548 | 1 象这种题目的iterative解法一般有什么套路那?
好像三种树(pre, in, postorder)的iterative traversal法都套不上啊? |
m**********g
发帖数: 153 | 2 把pre-order iterative traversal 改造了一下， 添加了 vector
nodePath; 作为path stack. 楼主看看是不是可以？
class Solution {
public:
void preorderTraversal(TreeNode *root) {
stack st;
vector nodePath;
if(root == NULL)
return;
st.push(root);
while(st.size()) {
TreeNode *tmp = st.top();
st.pop();
//leaf node, print the path from root to leaf
if(!tmp->right && !tmp->left) {
for(int i=0; i
cout<< nodePath[i].val;
cout<< tmp->val<
continue;
}
//clean the path backwards until parent is seen or path is empty.
while(!nodePath.empty()) {
TreeNode *parent = nodePath.back();
if(tmp == parent->left || tmp == parent->right)
break;
nodePath.pop_back();
}
//save this node in the path.
nodePath.push_back(tmp);
if(tmp->right)
st.push(tmp->right);
if(tmp->left)
st.push(tmp->left);
}
}
};
【在 h**o 的大作中提到】
: 象这种题目的iterative解法一般有什么套路那?
: 好像三种树(pre, in, postorder)的iterative traversal法都套不上啊?
|
w*******e
发帖数: 285 | 3 用bfs level print同时记住每个node的parent,看到leaf node就向上一直找到root
//none re-cursive level order, BFS
void levelorder(treenode* root){
if (root == nullptr) return;
map parent;
parent[root] = nullptr;
queue q;
q.push(root);
while (!q.empty()) {
auto cur = q.front(); q.pop();
if (cur->left) {
parent[cur->left] = cur;
q.push(cur->left);
}
if (cur->right) {
parent[cur->right] = cur;
q.push(cur->right);
}
//leaf node, print the path
if (!cur->left && !cur->right)
{
while(cur)
{
printf(cur->val);
cur = parent[cur];
}
}
}
}
【在 h**o 的大作中提到】
: 象这种题目的iterative解法一般有什么套路那?
: 好像三种树(pre, in, postorder)的iterative traversal法都套不上啊?
|
h**o
发帖数: 548 | 4 这个真好懂. 就是要费(n)空间
【在 w*******e 的大作中提到】
: 用bfs level print同时记住每个node的parent,看到leaf node就向上一直找到root
: //none re-cursive level order, BFS
: void levelorder(treenode* root){
: if (root == nullptr) return;
: map parent;
: parent[root] = nullptr;
: queue q;
: q.push(root);
: while (!q.empty()) {
: auto cur = q.front(); q.pop();
|
h**o
发帖数: 548 | 5 原来是这样.自己造不出这个path stack来.学习了.
把pre-order iterative traversal 改造了一下， 添加了 vector
nodePath; 作为path stack. 楼主看看是不是可以？
class Solution {
public:
void preorderTraversal(TreeNode *root) {
stack st;
vector nodePath;
if(root == NULL)
return;
st.push(root);
while(st.size()) {
TreeNode *tmp = st.top();
st.pop();
//leaf node, print the path from root to leaf
if(!tmp->right && !tmp->left) {
for(int i=0; i
cout<< nodePath[i].val;
cout<< tmp->val<
continue;
}
//clean the path backwards until parent is seen or path is empty.
while(!nodePath.empty()) {
TreeNode *parent = nodePath.back();
if(tmp == parent->left || tmp == parent->right)
break;
nodePath.pop_back();
}
//save this node in the path.
nodePath.push_back(tmp);
if(tmp->right)
st.push(tmp->right);
if(tmp->left)
st.push(tmp->left);
}
}
};
【在 m**********g 的大作中提到】
: 把pre-order iterative traversal 改造了一下， 添加了 vector
: nodePath; 作为path stack. 楼主看看是不是可以？
: class Solution {
: public:
: void preorderTraversal(TreeNode *root) {
: stack st;
: vector nodePath;
:
: if(root == NULL)
: return;
|
b*********s
发帖数: 115 | 6 preorder traversal, path存着从root到cur的所有点，如果cur是leaf则打印path
def printAllPaths(self, root):
stack = []
cur = root
path = []
while cur or stack:
if cur:
stack.append(cur)
path.append(cur)
if not cur.left and not cur.right:
print [node.val for node in path]
cur = cur.left
else:
cur = stack.pop()
while path[-1] is not cur:
path.pop()
cur = cur.right |
