617. Merge Two Binary Trees

这道题我觉得应该建一棵新树，答案update了tree1，我觉得有争议

 Version #2 Iteration[TODO]

如果可以更改原树的话Iteratino是比较简单的

但是建新树的话还没有想出好方法来做，可能需要一个parent map？

一刷 06/2022

Version #1 Recursion

Time O(N) - number of nodes

Space O(N) - int the worst case the depth of the stack could be number of nodes

Runtime: 1 ms, faster than 74.81% of Java online submissions for Merge Two Binary Trees.

Memory Usage: 51.5 MB, less than 10.80% of Java online submissions for Merge Two Binary Trees.

class Solution {

    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {

        if (root1 == null && root2 == null) {

            return null;

        }

        int sum = (root1 == null ? 0 : root1.val) + (root2 == null ? 0 : root2.val);

        TreeNode node = new TreeNode(sum);

        node.left = mergeTrees(root1 == null ? null : root1.left, root2 == null ? null : root2.left);

        node.right = mergeTrees(root1 == null ? null : root1.right, root2 == null ? null : root2.right);

        return node;

    }

}