DFS有遞歸與非遞歸兩種常見形式,BFS則通常為非遞歸的
本文使用
TreeNode.h
如下 struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};
1. DFS
遞歸法
以前序遞歸法為例
c++
class Solution {
public:
void preorder(TreeNode* root, vector<int> res){
if (!root) return;
res.push_back(root->val);
preorder(root->left, res);
preorder(root->right, res);
}
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
preorder(root, res);
return res;
}
};
中序後序遞歸隻需改變
preorder
函數的語句順序即可
非遞歸形式
仍以前序DFS為例
c++
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
vector<int> result;
st.push(root);
while (!st.empty()) {
TreeNode* node = st.top(); // 中
st.pop();
if (node != NULL) result.push_back(node->val);
else continue;
st.push(node->right); // 右
st.push(node->left); // 左
}
return result;
}
};
2. BFS
c++
#include<TreeNode.h>
#include<vector>
#include<queue>
using namespace std;
class Solution {
public:
vector<int> bfs(TreeNode* root) {
vector<int> res;
queue<TreeNode*> que;
que.push(root);
while (!que.empty()) {
TreeNode* tmpNode = que.front();
que.pop();
if (tmpNode->left != nullptr) {
que.push(tmpNode->left);
res.push_back(tmpNode->left->val);
}
if (tmpNode->right != nullptr) {
que.push(tmpNode->right);
res.push_back(tmpNode->right->val);
}
}
return res;
}
};
- 循環前初始化根結點進隊列
- 循環開始出隊一個元素
- 其後使左右孩子都進入隊列
- 隊列不為空時循環往複
層序周遊
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
queue<TreeNode*> que;
if (root != NULL) que.push(root);
vector<vector<int>> res;
while (!que.empty()) {
int size = que.size();
vector<int> vec; //準備工作
for(int i = 0; i < size; i++){ //内層才是明顯的bfs
TreeNode* node = que.front();
que.pop();
vec.push_back(node->val);
if (node->left) que.push(node->left);
if (node->right) que.push(node->right);
}
res.push_back(vec);
}
return res;
}
};