【leetcode刷題】29.合并二叉樹——Java版

前言

哈喽，大家好，我是一條。

糊塗算法，難得糊塗

簡單題倒數第二道！

Question

617. 合并二叉樹

難度：簡單

給定兩個二叉樹，想象當你将它們中的一個覆寫到另一個上時，兩個二叉樹的一些節點便會重疊。

你需要将他們合并為一個新的二叉樹。合并的規則是如果兩個節點重疊，那麼将他們的值相加作為節點合并後的新值，否則不為 NULL 的節點将直接作為新二叉樹的節點。

示例 1:

注意: 合并必須從兩個樹的根節點開始。

Solution

就像評論說的，遞歸少不了。

如果沒有頭緒的話，可以将這兩顆樹想象成是兩個數組

終止條件：樹 1 或者樹 2 的節點為 null

遞歸函數内：将兩個樹的節點相加，再遞歸的執行兩個樹的左節點，遞歸執行兩個樹的右節點

🤔思考一下如何不利用額外空間？

Code

所有leetcode代碼已同步至github

歡迎star

/**
 * @author yitiaoIT
 */
class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null) {
            return t2;
        }
        if (t2 == null) {
            return t1;
        }
        TreeNode merged = new TreeNode(t1.val + t2.val);
        merged.left = mergeTrees(t1.left, t2.left);
        merged.right = mergeTrees(t1.right, t2.right);
        return merged;
    }
}
      

Result

複雜度分析

• 時間複雜度：O(N)

🌈尋寶

⭐今天是堅持刷題更文的第29/100天

⭐各位的點贊、關注、收藏、評論、訂閱就是一條創作的最大動力

⭐更多算法題歡迎關注專欄《leetcode》

為了回饋各位粉絲，禮尚往來，給大家準備了一條多年積累下來的優質資源，包括 學習視訊、面試資料、珍藏電子書等

大家可以先自己找一下擷取方式，尋寶遊戲現在開始。

如果實在找不到可以評論區留言或私信我領取，不過一定要先關注哦！不然無法發私信！