617. Merge Two Binary Trees

dfs简单递归，可以先考虑三个点的情况写出来。

public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
    if (t1 == null || t2 == null) {
        return (t1 == null) ? t2 : t1;
    }
    TreeNode node = new TreeNode(t1.val + t2.val);
    node.left = mergeTrees(t1.left, t2.left);
    node.right = mergeTrees(t1.right, t2.right);
    return node;
}

bfs??...//./././????????

public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
    if (t1 == null) return t2;
    if (t2 == null) return t1;

    TreeNode root = new TreeNode(t1.val + t2.val);

    LinkedList<TreeNode> res = new LinkedList<>();
    res.add(root);

    LinkedList<TreeNode> list = new LinkedList<>();
    list.add(t1);
    list.add(t2);

    while (!res.isEmpty()) {
        TreeNode n1 = list.poll();
        TreeNode n2 = list.poll();
        TreeNode r = res.poll();

        if (n1.left != null && n2.left != null) {
            r.left = new TreeNode(n1.left.val + n2.left.val);
            res.add(r.left);

            list.add(n1.left);
            list.add(n2.left);
        } else if (n1.left != null) {
            r.left = n1.left;
        } else {
            r.left = n2.left;
        }

        if (n1.right != null && n2.right != null) {
            r.right = new TreeNode(n1.right.val + n2.right.val);
            res.add(r.right);

            list.add(n1.right);
            list.add(n2.right);
        } else if (n1.right != null) {
            r.right = n1.right;
        } else {
            r.right = n2.right;
        }
    }
    return root;
}

换成linkedlist会快点

public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
    if (t1 == null && t2 == null) return null;
    if (t1 == null || t2 == null) return t1 == null ? t2 : t1;
    ArrayDeque<TreeNode> q1 = new ArrayDeque<>();
    ArrayDeque<TreeNode> q2 = new ArrayDeque<>();

    q1.add(t1);
    q2.add(t2);

    TreeNode root = merge(t1, t2);
    ArrayDeque<TreeNode> res = new ArrayDeque<>();
    res.add(root);

    while (!q1.isEmpty() || !q2.isEmpty()) {
        TreeNode node1 = q1.remove();
        TreeNode node2 = q2.remove();
        TreeNode node = res.remove();

        node.left = merge(node1.left, node2.left);
        if (node1.left != null && node2.left != null) {
            res.add(node.left);
            q1.add(node1.left);
            q2.add(node2.left);
        }

        node.right = merge(node1.right, node2.right);
        if (node1.right != null && node2.right != null) {
            res.add(node.right);  
            q1.add(node1.right);
            q2.add(node2.right);
        }
    }
    return root;
}

private TreeNode merge(TreeNode p, TreeNode q) {
    if (p == null && q == null) return null;
    if (p == null || q == null) return (p == null) ? q : p;
    return new TreeNode(p.val + q.val);
}