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

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

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

題目描述

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

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

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

加法規(guī)則如下:

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

提示:

示例 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é)點(diǎn)，這些節(jié)點(diǎn)的值為 val，題目規(guī)定根節(jié)點(diǎn)所在層位 1，且插入節(jié)點(diǎn) val 的時(shí)候，原來節(jié)點(diǎn)的左子樹要連接在新節(jié)點(diǎn)的左子樹上，原來節(jié)點(diǎn)的右子樹要連接在新節(jié)點(diǎn)的右子樹上。

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

解題思路分析

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

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

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

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

具體實(shí)現(xiàn)

常規(guī)的二叉樹搜索，在對(duì)整棵二叉樹進(jìn)行搜索的同時(shí)維護(hù)當(dāng)前樹的深度即可，在第 depth 按照題意進(jìn)行插入節(jié)點(diǎn)即可。

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

復(fù)雜度分析

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

代碼實(shí)現(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 記錄當(dāng)前層數(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 層時(shí)開始插入元素 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é)點(diǎn)元素
            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);
        }
        // 當(dāng) depth 到第 2 層時(shí)表示 在當(dāng)前層的下一層插入節(jié)點(diǎn) 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;
    }
};

總結(jié)

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