leetcode-0617 合并二叉树

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目地址https://leetcode-cn.com/problems/merge-two-binary-trees/

1.递归解法

递归的话我们首先需要递归的终止条件，对于本题而言，递归的终止条件是t1和t2递归到任意一方为null的情况，因为这种条件下，我们不需要继续合并下去，直接返回不为null那一方即可。整体递归的过程就比较简单了，分为三个步骤

求根节点本身
求根节点的左孩子节点
求根节点的右孩子节点

算法整体的时间复杂度为O(n) 空间复杂度为O(h) 其中h为二叉树的最大深度

var mergeTrees = function(t1, t2) {

    if (t1 == null) return t2;

    if (t2 == null) return t1;

    const newRoot = new TreeNode(t1.val + t2.val);

    newRoot.left = mergeTrees(t1.left, t2.left);

    newRoot.right = mergeTrees(t1.right, t2.right);

    return newRoot;

};

2.DFS

这种解法以t1为基准，直接在t1上面操作，最终将t1返回。时间复杂度O(n) 空间复杂度O(n)。

var mergeTrees = function(t1, t2) {

    if (t1 === null) return t2;

    if (t2 === null) return t1;

    const stack = [[t1, t2]];

    while (stack.length > 0) {

        let [a, b] = stack.pop();

        // 如果b为null，那无论a是否为空，a都不需要做出改变

        if (b === null) continue;

        a.val = a.val + b.val;

        // 下面处理a和b的子节点

        // 如果a的左孩子或者右孩子为null，那直接将其赋值为b的左孩子或者右孩子

        if (a.left === null)

            a.left = b.left;

        else

            stack.push([a.left, b.left])

        if (a.right === null)

            a.right = b.right

        else

            stack.push([a.right, b.right])

    }

    return t1;

};

3.BFS

这里基本上是和DFS一样，因为不需要在意遍历的顺序，只需要将每个节点都遍历到，因此也可以使用BFS。时间复杂度O(n) 空间复杂度O(n)。

class Solution {

    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {

        Queue<TreeNode[]> queue = new LinkedList<>();

        if (t1 == null) return t2;

        if (t2 == null) return t1;

        queue.offer(new TreeNode[]{t1, t2});

        while (!queue.isEmpty()) {

            TreeNode[] t = queue.poll();

            if (t[1] == null) continue;

            t[0].val += t[1].val;

            if (t[0].left == null)

                t[0].left = t[1].left;

            else

                queue.offer(new TreeNode[]{t[0].left, t[1].left});

            if (t[0].right == null)

                t[0].right = t[1].right;

            else

                queue.offer(new TreeNode[]{t[0].right, t[1].right});

        }

        return t1;

    }

}