617. Merge Two Binary Trees

https://leetcode.com/problems/merge-two-binary-trees/description/

Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.

You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.

Thoughts

合并两棵树，相同位置结点值相加，没有结点则看作值为0。二叉树=>分治，根据题意合并当前节点，并分治合并左右并再作为当前结点左右子树。

Code

/*
 * @lc app=leetcode id=617 lang=cpp
 *
 * [617] Merge Two Binary Trees
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (t1 == nullptr && t2 == nullptr) return nullptr;
        int val = (t1 == nullptr ? 0 : t1->val) + (t2 == nullptr ? 0 : t2->val);
        TreeNode *node = new TreeNode(val);
        node->left = mergeTrees(t1 == nullptr ? nullptr : t1->left, t2 == nullptr ? nullptr : t2->left);   
        node->right = mergeTrees(t1 == nullptr ? nullptr : t1->right, t2 == nullptr ? nullptr : t2->right);   
        return node;   
    }
};
// @lc code=end

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null) {
            return null;
        }
        TreeNode node = new TreeNode((t1 == null ? 0 : t1.val) + (t2 == null ? 0 : t2.val));
        node.left = mergeTrees(t1 == null ? null : t1.left, t2 == null ? null : t2.left);
        node.right = mergeTrees(t1 == null ? null : t1.right, t2 == null ? null : t2.right);
        return node;
    }
}

Analysis

时间复杂度为O(m + n), m和n分别为t1, t2的节点数。

Ver. 2

用stack实现的pre-order traversal做, 对t1和t2都弄一个栈, 并且及时其中有个节点是null也push进去以确保遍历同进退, 结构一致.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null) {
            return null;
        }
        Stack<TreeNode> s = new Stack<>(), s1 = new Stack<>(), s2 = new Stack<>();
        s1.push(t1);
        s2.push(t2);
        TreeNode root = new TreeNode((t1 == null ? 0 : t1.val) + (t2 == null ? 0 : t2.val));
        s.push(root);
        while (!s.isEmpty()) {
            TreeNode node = s.pop();
            TreeNode n1 = s1.pop();
            TreeNode n2 = s2.pop();

            if (n1 != null && n1.right != null || n2 != null && n2.right != null) {
                node.right = new TreeNode((n1 == null || n1.right == null ? 0 : n1.right.val) + 
                                                (n2 == null || n2.right == null ? 0 : n2.right.val));
                s.push(node.right);
                s1.push(n1 == null ? null : n1.right);
                s2.push(n2 == null ? null : n2.right);
            }

            if (n1 != null && n1.left != null || n2 != null && n2.left != null) {
                node.left = new TreeNode((n1 == null || n1.left == null ? 0 : n1.left.val) +   
                                                (n2 == null || n2.left == null ? 0 : n2.left.val));
                s.push(node.left);
                s1.push(n1 == null ? null : n1.left);
                s2.push(n2 == null ? null : n2.left);
            }
        }

        return root;
    }
}

Ver. 3

https://discuss.leetcode.com/topic/92306/c-o-n-space-iterative-solution-no-new-tree

不用新建个树. 时间O(N)空间O(h). 当n1.left为null而n2.left不为null时, 直接把n2.left拼过来即可.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null) {
            return t2;
        } else if (t2 == null) {
            return t1;
        } 
        Stack<TreeNode> s1 = new Stack<>(), s2 = new Stack<>();
        s1.push(t1);
        s2.push(t2);
        while (!s1.isEmpty()) {
            TreeNode n1 = s1.pop();
            TreeNode n2 = s2.pop();

            n1.val += n2.val;
            if (n1.right == null && n2.right != null) {
                n1.right = n2.right;
            } else if (n1.right != null && n2.right != null) {
                s1.push(n1.right);
                s2.push(n2.right);
            }

            if (n1.left == null && n2.left != null) {
                n1.left = n2.left;
            } else if (n1.left != null && n2.left != null) {
                s1.push(n1.left);
                s2.push(n2.left);
            }
        }

        return t1;
    }
}