C C++ LeetCode題解在二叉樹中增加一行示例詳解

更新時間：2022年10月12日 11:41:58 作者：Junkman丶

這篇文章主要為大家介紹了C C++ LeetCode題解在二叉樹中增加一行示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪

題目描述

題目鏈接：623. 在二叉樹中增加一行

給定一個二叉樹的根 root 和兩個整數(shù) val 和 depth ，在給定的深度 depth 處添加一個值為 val 的節(jié)點行。

注意，根節(jié)點 root 位于深度 1 。

加法規(guī)則如下:

給定整數(shù) depth，對于深度為 depth - 1 的每個非空樹節(jié)點 cur ，創(chuàng)建兩個值為 val 的樹節(jié)點作為 cur 的左子樹根和右子樹根。
cur 原來的左子樹應該是新的左子樹根的左子樹。
cur 原來的右子樹應該是新的右子樹根的右子樹。
如果 depth == 1 意味著 depth - 1 根本沒有深度，那么創(chuàng)建一個樹節(jié)點，值 val 作為整個原始樹的新根，而原始樹就是新根的左子樹。

提示:

示例 1：

輸入: root = [4,2,6,3,1,5], val = 1, depth = 2

輸出: [4,1,1,2,null,null,6,3,1,5]

示例 2：

輸入: root = [4,2,null,3,1], val = 1, depth = 3

輸出: [4,2,null,1,1,3,null,null,1]

整理題意

題目給定一棵二叉樹，要求我們在深度為 depth 的位置插入一行節(jié)點，這些節(jié)點的值為 val，題目規(guī)定根節(jié)點所在層位 1，且插入節(jié)點 val 的時候，原來節(jié)點的左子樹要連接在新節(jié)點的左子樹上，原來節(jié)點的右子樹要連接在新節(jié)點的右子樹上。

需要特別注意 depth = 1 的情況，此時將新節(jié)點作為根節(jié)點，將原來的根節(jié)點連接在新節(jié)點的左子樹上。

解題思路分析

層序遍歷（廣度優(yōu)先搜索）

根據(jù)題意描述，很容易想到使用 BFS 對整棵樹進行層序遍歷，在遍歷到第 depth - 1 層時按照題意進行插入節(jié)點即可。

遞歸（深度優(yōu)先搜索）

該題還可以通過給定的函數(shù)本身進行遞歸完成，在遞歸的過程中不斷維護當前 depth 的值，當 depth 的值為 2 時進行節(jié)點的插入即可。

具體實現(xiàn)

常規(guī)的二叉樹搜索，在對整棵二叉樹進行搜索的同時維護當前樹的深度即可，在第 depth 按照題意進行插入節(jié)點即可。

在實現(xiàn)過程中需要注意特判 depth = 1 的情況，也就是當插入的層數(shù)為 1 時，需要將根節(jié)點放在新插入節(jié)點的左子樹上，并返回新插入的這個節(jié)點。

復雜度分析

時間復雜度：O(n)，其中 n 為輸入的樹的節(jié)點數(shù)。最壞情況下，需要遍歷整棵樹。
空間復雜度：O(n)，在層序遍歷中隊列空間開銷最多為 O(n)，遞歸的深度最多為 O(n)。

代碼實現(xiàn)

層序遍歷（廣度優(yōu)先搜索）

/**
 * Definition for a binary tree node.
 * 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) {}
 * };
 */
class Solution {
public:
    TreeNode* addOneRow(TreeNode* root, int val, int depth) {
        // 特判 depth = 1 的情況
        if(depth == 1){
            TreeNode *res = new TreeNode(val);
            res->left = root;
            return res;
        }
        // k 記錄當前層數(shù)
        int k = 1;
        queue<TreeNode*> que;
        while(que.size()) que.pop();
        que.push(root);
        // bfs層序遍歷
        while(que.size()){
            int n = que.size();
            // 遍歷到 depth - 1 層時開始插入元素 val
            if(k == depth - 1){
                for(int i = 0; i < n; i++){
                    TreeNode *now = que.front();
                    que.pop();
                    TreeNode *l = new TreeNode(val, now->left, NULL);
                    TreeNode *r = new TreeNode(val, NULL, now->right);
                    now->left = l;
                    now->right = r;
                }
                // 插入完成后跳出
                break;
            }
            // 壓入下一層節(jié)點元素
            for(int i = 0; i < n; i++){
                TreeNode *now = que.front();
                que.pop();
                if(now->left != NULL) que.push(now->left);
                if(now->right != NULL) que.push(now->right);
            }
            k++;
        }
        return root;
    }
};

遞歸（深度優(yōu)先搜索）

/**
 * Definition for a binary tree node.
 * 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) {}
 * };
 */
class Solution {
public:
    TreeNode* addOneRow(TreeNode* root, int val, int depth) {
        if(root == nullptr) return root;
        // 特判 depth = 1 的情況
        if(depth == 1){
            return new TreeNode(val, root, nullptr);
        }
        // 當 depth 到第 2 層時表示 在當前層的下一層插入節(jié)點 val
        if(depth == 2){
            root->left = new TreeNode(val, root->left, nullptr);
            root->right = new TreeNode(val, nullptr, root->right);
            return root;
        }
        // 否則一直遞歸
        else{
            root->left = addOneRow(root->left, val, depth - 1);
            root->right = addOneRow(root->right, val, depth - 1);
        }
        return root;
    }
};

總結

該題為常規(guī)的搜索題，既可以使用廣度優(yōu)先搜索進行層序遍歷來完成，也可以使用深度優(yōu)先搜索來遞歸完成，因為題目描述為插入一層元素節(jié)點，很容易想到層序遍歷，而遞歸的方法較難想到，在實現(xiàn)過程中可以嘗試使用遞歸的方式來完成，可以鍛煉遞歸的思維以及在實現(xiàn)遞歸時的各種邊界考慮。同時遞歸的代碼也比層序遍歷的代碼更為簡潔。
測試結果：