快捷導(dǎo)航

C++合并二叉樹的思路與示例代碼

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

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

前言

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

示例 1:

思路

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

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

代碼如下：

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

2.確定終止條件：

因為是傳入了兩個樹，那么就有兩個樹遍歷的節(jié)點(diǎn)t1 和 t2，如果t1 == NULL 了，兩個樹合并就應(yīng)該是 t2 了?。ㄈ绻鹴2也為NULL也無所謂，合并之后就是NULL）。

反過來如果t2 == NULL，那么兩個數(shù)合并就是t1（如果t1也為NULL也無所謂，合并之后就是NULL）。

代碼如下：

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

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

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

t1->val += t2->val;

接下來t1 的左子樹是：合并 t1左子樹 t2左子樹之后的左子樹。

t1 的右子樹：是合并 t1右子樹 t2右子樹之后的右子樹。

最終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;
    }
};

附：新建一顆樹

不破壞原有兩顆樹結(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;
    }
};