快捷導(dǎo)航

C++合并二叉樹(shù)的思路與示例代碼

更新時(shí)間：2021年08月06日 10:14:08 作者：久病成良醫(yī)

二叉樹(shù)大家應(yīng)該都不陌生,但是合并二叉樹(shù)呢?這篇文章主要給大家介紹了關(guān)于C++合并二叉樹(shù)的相關(guān)資料,文中給出了兩種解決的方法,大家可以根據(jù)需要選擇對(duì)應(yīng)的方法,需要的朋友可以參考下

前言

給定兩個(gè)二叉樹(shù)，想象當(dāng)你將它們中的一個(gè)覆蓋到另一個(gè)上時(shí)，兩個(gè)二叉樹(shù)的一些節(jié)點(diǎn)便會(huì)重疊。你需要將他們合并為一個(gè)新的二叉樹(shù)。合并的規(guī)則是如果兩個(gè)節(jié)點(diǎn)重疊，那么將他們的值相加作為節(jié)點(diǎn)合并后的新值，否則不為 NULL 的節(jié)點(diǎn)將直接作為新二叉樹(shù)的節(jié)點(diǎn)。

示例 1:

思路

1.確定遞歸函數(shù)的參數(shù)和返回值：

首先那么要合入兩個(gè)二叉樹(shù)，那么參數(shù)至少是要傳入兩個(gè)二叉樹(shù)的根節(jié)點(diǎn)，返回值就是合并之后二叉樹(shù)的根節(jié)點(diǎn)。

代碼如下：

TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2)

2.確定終止條件：

因?yàn)槭莻魅肓藘蓚€(gè)樹(shù)，那么就有兩個(gè)樹(shù)遍歷的節(jié)點(diǎn)t1 和 t2，如果t1 == NULL 了，兩個(gè)樹(shù)合并就應(yīng)該是 t2 了啊（如果t2也為NULL也無(wú)所謂，合并之后就是NULL）。

反過(guò)來(lái)如果t2 == NULL，那么兩個(gè)數(shù)合并就是t1（如果t1也為NULL也無(wú)所謂，合并之后就是NULL）。

代碼如下：

if (t1 == NULL) return t2; // 如果t1為空，合并之后就應(yīng)該是t2
if (t2 == NULL) return t1; // 如果t2為空，合并之后就應(yīng)該是t1

3.確定單層遞歸的邏輯：

單層遞歸的邏輯就比較好些了，這里我們用重復(fù)利用一下t1這個(gè)樹(shù)，t1就是合并之后樹(shù)的根節(jié)點(diǎn)（就是修改了原來(lái)樹(shù)的結(jié)構(gòu)）。
那么單層遞歸中，就要把兩棵樹(shù)的元素加到一起。

t1->val += t2->val;

接下來(lái)t1 的左子樹(shù)是：合并 t1左子樹(shù) t2左子樹(shù)之后的左子樹(shù)。

t1 的右子樹(shù)：是合并 t1右子樹(shù) t2右子樹(shù)之后的右子樹(shù)。

最終t1就是合并之后的根節(jié)點(diǎn)。

/**
 * 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* mergeTrees(TreeNode* root1, TreeNode* root2) {
        // 判空
        if(root1==nullptr) return root2;
        if(root2==nullptr) return root1;

        // 修改了t1的數(shù)值和結(jié)構(gòu)
        root1->val+=root2->val;
        root1->left=mergeTrees(root1->left,root2->left);
        root1->right=mergeTrees(root1->right,root2->right);
        
        return root1;
    }
};

附：新建一顆樹(shù)

不破壞原有兩顆樹(shù)結(jié)構(gòu)

/**
 * 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:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if(!t1&&!t2)
            return NULL;
        TreeNode* node=new TreeNode(0);
        node->val=(t1? t1->val:0)+(t2? t2->val:0);
        node->left=mergeTrees((t1? t1->left: NULL),(t2? t2->left:NULL));
        node->right=mergeTrees((t1? t1->right: NULL),(t2? t2->right : NULL));
        return node;
    }
};