leetcode617.合并二叉樹

class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        TreeNode node = DFS(null, t1, t2, 0);
        return node;
    }

    public TreeNode DFS(TreeNode res, TreeNode resChild, TreeNode followChild, int leftOrRightFlag) {
        if (Objects.nonNull(resChild) && Objects.nonNull(followChild)) {
            // 都不為空
            resChild.val += followChild.val;
            TreeNode leftChild = DFS(resChild, resChild.left, followChild.left, 1);
            TreeNode rightChild = DFS(resChild, resChild.right, followChild.right, 2);
            resChild.left = leftChild;
            resChild.right = rightChild;
        } else if (Objects.isNull(resChild) && Objects.nonNull(followChild)) {
            // followChild 不為空
            TreeNode child = new TreeNode(followChild.val);
            if (leftOrRightFlag == 1) {
                res.left = child;
                resChild = child;
            } else if (leftOrRightFlag == 2) {
                res.right = child;
                resChild = child;
            } else {
                resChild = child;
            }
            TreeNode leftChild = DFS(resChild, resChild.left, followChild.left, 1);
            TreeNode rightChild = DFS(resChild, resChild.right, followChild.right, 2);
            resChild.left = leftChild;
            resChild.right = rightChild;
        }
        return resChild;
    }
}
           

上面寫的太臃腫了，沒有用到遞歸的精髓。

下面的就好了

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;
    }
}
           

以上是DFS解法

用BFS解法如下：

// 廣度優先算法
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        Queue<TreeNode> queue = new LinkedList<>();
        Queue<TreeNode> firstQueue = new LinkedList<>();
        Queue<TreeNode> secondQueue = new LinkedList<>();
        if (Objects.isNull(t1)) {
            return t2;
        }
        if (Objects.isNull(t2)) {
            return t1;
        }
        firstQueue.add(t1);
        secondQueue.add(t2);
        TreeNode mergeNode = new TreeNode(t1.val + t2.val);
        queue.add(mergeNode);
        TreeNode res = queue.peek();
        while (!firstQueue.isEmpty()) {
            TreeNode first = firstQueue.poll();
            TreeNode second = secondQueue.poll();
            TreeNode resCopy = queue.poll();
            // 先對左孩子進行處理
            if (Objects.nonNull(first.left) && Objects.isNull(second.left)) {
                // 沒必要入隊列了
                TreeNode firstCopy = new TreeNode(first.left.val);
                firstCopy.left = first.left.left;
                firstCopy.right = first.left.right;
                resCopy.left = firstCopy;
            } else if (Objects.nonNull(second.left) && Objects.isNull(first.left)) {
                TreeNode secondCopy = new TreeNode(second.left.val);
                secondCopy.left = second.left.left;
                secondCopy.right = second.left.right;
                resCopy.left = secondCopy;
            } else if (Objects.nonNull(first.left) && Objects.nonNull(second.left)) {
                firstQueue.add(first.left);
                secondQueue.add(second.left);
                TreeNode mergeNode2 = new TreeNode(first.left.val + second.left.val);
                queue.add(mergeNode2);
                resCopy.left = mergeNode2;
            }

            // 再對右孩子進行處理
            if (Objects.nonNull(first.right) && Objects.isNull(second.right)) {
                TreeNode firstCopy = new TreeNode(first.right.val);
                firstCopy.left = first.right.left;
                firstCopy.right = first.right.right;
                resCopy.right = firstCopy;
            } else if (Objects.isNull(first.right) && Objects.nonNull(second.right)) {
                TreeNode secondCopy = new TreeNode(second.right.val);
                secondCopy.left = second.right.left;
                secondCopy.right = second.right.right;
                resCopy.right = secondCopy;
            } else if (Objects.nonNull(first.right) && Objects.nonNull(second.right)) {
                firstQueue.add(first.right);
                secondQueue.add(second.right);
                TreeNode mergeNode2 = new TreeNode(first.right.val + second.right.val);
                queue.add(mergeNode2);
                resCopy.right = mergeNode2;
            }
        }
        return res;
    }