首页 > 代码库 > bfs-dfs-bst
bfs-dfs-bst
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
bfs :
void bfs(TreeNode *root) { if(root==NULL) return; queue<TreeNode *> x; TreeNode *t; x.push(root); while(!x.empty()){ t = x.front(); if(t->left!=NULL) x.push(t->left); if(t->right!=NULL) x.push(x->right); // do something x.pop(); } }递归dfs:
void dfs(TreeNode *root) { if(root==NULL) return; if(root->left != NULL) dfs(root->left); if(root->right != NULL) dfs(root->right); // do something }迭代dfs, post_order traverse,稍微修改left,right顺序,就是previous_order traverse
void dfs(TreeNode *root) { if(root==NULL) return; stack<TreeNode *> x; unorder<TreeNode *,bool> m; x.push(root); while(!x.empty()){ t = x.top(); if(t->left != NULL && m[t->left] == 0) x.push(t->left); else if(t->right != NULL && m[t->right] == 0) x.push(t->right); else{ // do something m[t] = 1; x.pop(); } } }递归inorder
void inorder(TreeNode *root) { if(root==NULL) return; if(root->left != NULL) inorder(root->left); // do something with root if(root->right != NULL) inorder(root->right); }迭代inorder
void inorder(TreeNode *root) { if(root==NULL) return; stack<TreeNode *> x; unordered_map<TreeNode *,bool> m; TreeNode *t; x.push(back); while(!x.empty()){ t = x.top(); if(t->left != NULL && m[t->left] == 0){ t = t-left; x.push(t); } else{ x.pop(); m[t] = 1; // do something if(t->right != NULL) x.push(t->right); } } }
bfs-dfs-bst
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。