C++二叉樹的直徑與合并詳解

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

這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)二叉樹基本操作，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能給你帶來幫助

二叉樹的直徑

給定一棵二叉樹，你需要計(jì)算它的直徑長(zhǎng)度。一棵二叉樹的直徑長(zhǎng)度是任意兩個(gè)結(jié)點(diǎn)路徑長(zhǎng)度中的最大值。這條路徑可能穿過也可能不穿過根結(jié)點(diǎn)。

示例 :

給定二叉樹

在這里插入圖片描述

返回 3, 它的長(zhǎng)度是路徑 [4,2,1,3] 或者 [5,2,1,3]。

思路

求左右孩子深度的和的最大值

/**
 * 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:
    int res=0; //定義一個(gè)全局變量
    int depth(TreeNode* root){  //求深度
        if(root==nullptr)  return 0;
        int L=depth(root->left); 
        int R=depth(root->right);
        res=max(res,L+R);
        return max(L,R)+1;
    }
    int diameterOfBinaryTree(TreeNode* root) {
        depth(root);
        return res;
    }
};

合并二叉樹

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

示例 1:

在這里插入圖片描述

思路

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

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

代碼如下：

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

2.確定終止條件：

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

反過來如果t2 == NULL，那么兩個(gè)數(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這個(gè)樹，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;
    }
};