LeetCode 623. 在二叉树中增加一行 深度优先搜索 (dfs) 广度优先搜索 (bfs) C++

①共同点：在搜索中将起点存入数据结构，然后重复以下步骤直到数据结构被清空：

• 取其中的下一个顶点并标记它；
• 将其所有相邻而又未被标记的顶点加入数据结构。

②区别：从数据结构中获取下一个顶点的规则不同：对广度优先搜索来说是最早加入的顶点，对于深度优先搜索来说是最晚加入的顶点。

深度优先搜索探索一幅图的方式是寻找离起点更远的顶点，只是在碰到死胡同时才访问近处的顶点；广度优先搜索则会首先覆盖起点附近的顶点，只在邻近的所有顶点都被访问了之后才向前进。

深度优先搜索的路径通常较长而且曲折，广度优先搜索的路径则短而直接。

解法一：深度优先搜索

class Solution {
public:
    void bfs(TreeNode* root, int val, int depth, int curDepth)
    {
        if (root == nullptr) return;
        if (curDepth == depth-1)
        {
            TreeNode* left = new TreeNode(val);
            TreeNode* right = new TreeNode(val);
            left->left = root->left;
            right->right = root->right;
            root->left = left;
            root->right = right;
        }
        else
        {
            bfs(root->left, val, depth, curDepth+1);
            bfs(root->right, val, depth, curDepth+1);
        }
    }

    TreeNode* addOneRow(TreeNode* root, int val, int depth) {
        if (depth == 1)
        {
            TreeNode* newRoot = new TreeNode(val);
            newRoot->left = root;
            return newRoot;
        }

        bfs(root, val, depth, 1);
        return root;
    }
};

解法二：广度优先搜索

class Solution {
public:
    TreeNode* addOneRow(TreeNode* root, int val, int depth) {
        if(depth==1) return new TreeNode(val,root,nullptr);
        
        queue qu;
        qu.emplace(root);
        int h=1;
        while((!qu.empty())&&h!=depth){
            int l=qu.size();
            h++;
            while(l--){
                TreeNode* p=qu.front();
                qu.pop(); 
                if(p->left) qu.emplace(p->left);
                if(p->right) qu.emplace(p->right);
                if(h==depth){
                    p->left=new TreeNode(val,p->left,nullptr);
                    p->right=new TreeNode(val,nullptr,p->right);
                }
            }
        }
        return root;
    }
};