做外贸门户网站,一般人公司注册费用,极简风格 wordpress,odoo做网站修改一下深度优先算法和广度优先算法#xff0c;标出每一个节点相对于遍历起始位置的层级#xff0c;遍历起始起点为第一层#xff0c;和第一层相连的节点为第二层#xff0c;以此类推
定义一个新的结构
struct NodeWithLevel {TreeNode* node;int level;NodeWithLevel(T…修改一下深度优先算法和广度优先算法标出每一个节点相对于遍历起始位置的层级遍历起始起点为第一层和第一层相连的节点为第二层以此类推
定义一个新的结构
struct NodeWithLevel {TreeNode* node;int level;NodeWithLevel(TreeNode* n, int l) : node(n), level(l) {}
};
深度优先搜索DFS
class Solution {
public:vectorNodeWithLevel dfsWithLevel(TreeNode* root) {vectorNodeWithLevel result;dfsHelper(root, 1, result);return result;}private:void dfsHelper(TreeNode* node, int level, vectorNodeWithLevel result) {if (node nullptr) {return;}// 将当前节点及其层级添加到结果中result.push_back(NodeWithLevel(node, level));// 递归处理左子树层级加1dfsHelper(node-left, level 1, result);// 递归处理右子树层级加1dfsHelper(node-right, level 1, result);}
};
DFS算法的工作原理
我们使用一个辅助函数 dfsHelper它接受当前节点、当前层级和结果vector作为参数。如果当前节点为空我们直接返回。我们将当前节点和其层级添加到结果中。然后我们递归地处理左子树和右子树每次递归时层级加1。
广度优先搜索BFS:
class Solution {
public:vectorNodeWithLevel bfsWithLevel(TreeNode* root) {vectorNodeWithLevel result;if (root nullptr) {return result;}queueNodeWithLevel q;q.push(NodeWithLevel(root, 1));while (!q.empty()) {NodeWithLevel current q.front();q.pop();// 将当前节点及其层级添加到结果中result.push_back(current);// 如果左子节点存在将其加入队列层级加1if (current.node-left) {q.push(NodeWithLevel(current.node-left, current.level 1));}// 如果右子节点存在将其加入队列层级加1if (current.node-right) {q.push(NodeWithLevel(current.node-right, current.level 1));}}return result;}
};
这个BFS算法的工作原理
我们创建一个队列来存储 NodeWithLevel 对象。我们从根节点开始将其作为第一层加入队列。当队列不为空时我们取出队首元素将其添加到结果中。然后我们检查当前节点的左右子节点如果存在就将它们加入队列层级为当前节点的层级加1。重复这个过程直到队列为空。
这两种算法都会返回一个 vectorNodeWithLevel其中包含了树中所有节点及其对应的层级。DFS 通常会以前序遍历的顺序返回节点而 BFS 会按照层序遍历的顺序返回节点。
