leetcode-0617 合併二叉樹

• 2020 年 4 月 24 日
• 筆記
• 【*****演算法*****】

題目地址//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;
    }
}

更多LeetCode題解和數據結構方面的內容，可以關注我的github，求個star~ ▄█▔▉●