C++ 编程练习题: 如何合并两个二叉树?

 * 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) {
        TreeNode* root;
        if (t1 == NULL) return t2;
        if (t2 == NULL) return t1;
        root = new TreeNode(t1->val + t2->val);
        root->left = mergeTrees(t1->left, t2->left);
        root->right = mergeTrees(t1->right, t2->right);
        return root;
    }
};

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (t1 == nullptr) return t2;
        if (t2 == nullptr) return t1;
        t1->val += t2-gt;val;
        t1->left = mergeTrees(t1->left, t2->left);
        t1->right = mergeTrees(t1->right, t2->right);
        return t1;
    }
};

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (t1 == nullptr) return t2;
        if (t2 == nullptr) return t1;
        stack< pair<TreeNode*, TreeNode*> > st;
        st.push(make_pair(t1, t2));
        while (st.size() > 0) {
            auto cur = st.top();
            st.pop();
            if (cur.first == nullptr || cur.second == nullptr) {
                continue;
            }
            cur.first->val += cur.second->val; // 累加值
            if (cur.first->left == nullptr) { // 第一颗树的左树为空, 那么就用第二颗树的左树
                cur.first->left = cur.second->left;
            } else {
                st.push(make_pair(cur.first->left, cur.second->left));
            }
            if (cur.first->right == nullptr) { // 第一颗树的右树为空, 那么就用第二颗树的右树
                cur.first->right = cur.second->right;
            } else {
                st.push(make_pair(cur.first->right, cur.second->right));
            }
        }       
        return t1;
    }
};