617. Merge Two Binary Trees - Easy

前往題目

想法

• 建立新的樹，每個節點的值相加

思路

遞迴

1. 遇到root1或root2其中一個是null就回傳另一個，兩個都是null也無所謂，因為就是把null加到樹上
2. 兩個節點的值相加
3. 左右節點再次呼叫方法
4. 回傳當前節點

Code

網友解答

但是這個方法挪用了舊的樹，也就是root1，題目想要我們merge them into a new binary tree

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null) return root2;
        if (root2 == null) return root1;

        // Sum up the current nodes
        root1.val += root2.val;
        // Build the left and right nodes
        root1.left = mergeTrees(root1.left, root2.left);
        root1.right = mergeTrees(root1.right, root2.right);
        return root1;
    }
}

建立新的樹

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 == null) return null;

        // In case a null node present
        int val1 = root1 != null ? root1.val : 0;
        int val2 = root2 != null ? root2.val : 0;

        // Build the new tree
        TreeNode res = new TreeNode(val1 + val2);

        res.left = mergeTrees(root1 != null ? root1.left : null, root2 != null ? root2.left : null);
        res.right = mergeTrees(root1 != null ? root1.right : null, root2 != null ? root2.right : null);

        return res;
    }
}