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

Posted on by

二叉樹的直徑

給定一棵二叉樹，你需要計算它的直徑長度。一棵二叉樹的直徑長度是任意兩個結點路徑長度中的最大值。這條路徑可能穿過也可能不穿過根結點。

示例 :

給定二叉樹

在這裡插入圖片描述

返回 3, 它的長度是路徑 [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; //定義一個全局變量
    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;
    }
};

合並二叉樹

給定兩個二叉樹，想象當你將它們中的一個覆蓋到另一個上時，兩個二叉樹的一些節點便會重疊。你需要將他們合並為一個新的二叉樹。合並的規則是如果兩個節點重疊，那麼將他們的值相加作為節點合並後的新值，否則不為 NULL 的節點將直接作為新二叉樹的節點。

示例 1:

在這裡插入圖片描述

思路

1.確定遞歸函數的參數和返回值：

首先那麼要合入兩個二叉樹，那麼參數至少是要傳入兩個二叉樹的根節點，返回值就是合並之後二叉樹的根節點。

代碼如下：

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

2.確定終止條件：

因為是傳入瞭兩個樹，那麼就有兩個樹遍歷的節點t1 和 t2，如果t1 == NULL 瞭，兩個樹合並就應該是 t2 瞭啊（如果t2也為NULL也無所謂，合並之後就是NULL）。

反過來如果t2 == NULL，那麼兩個數合並就是t1（如果t1也為NULL也無所謂，合並之後就是NULL）。

代碼如下：

if (t1 == NULL) return t2; // 如果t1為空，合並之後就應該是t2
if (t2 == NULL) return t1; // 如果t2為空，合並之後就應該是t1

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

單層遞歸的邏輯就比較好些瞭，這裡我們用重復利用一下t1這個樹，t1就是合並之後樹的根節點（就是修改瞭原來樹的結構）。
那麼單層遞歸中，就要把兩棵樹的元素加到一起。

t1->val += t2->val;

接下來t1 的左子樹是：合並 t1左子樹 t2左子樹之後的左子樹。

t1 的右子樹：是 合並 t1右子樹 t2右子樹之後的右子樹。

最終t1就是合並之後的根節點。

/**
 * 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的數值和結構
        root1->val+=root2->val;
        root1->left=mergeTrees(root1->left,root2->left);
        root1->right=mergeTrees(root1->right,root2->right);
        return root1;
    }
};

總結

本篇文章就到這裡瞭，希望能給你帶來幫助，也希望您能夠多多關註WalkonNet的更多內容!

推薦閱讀：