101、【树与二叉树】leetcode ——617. 合并二叉树：递归法+迭代法（C++版本）

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

题目描述

解题思路

一、递归法

先序遍历

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if(!root1)          return root2;
        if(!root2)          return root1;
        // 此位置上两个树都存在结点时相加 
        root1->val = root1->val + root2->val;
        root1->left = mergeTrees(root1->left, root2->left);
        root1->right = mergeTrees(root1->right, root2->right);        
        return root1;
    }
};

二、迭代法

先序遍历

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if(!root1)          return root2;
        if(!root2)          return root1;
        stack<TreeNode*> st;                
        st.push(root2);
        st.push(root1);
        while(!st.empty()) {            
            TreeNode* node1 = st.top();     st.pop();
            TreeNode* node2 = st.top();     st.pop();            
            node1->val = node1->val + node2->val;
            if(node1->right && node2->right) {                
                st.push(node2->right);
                st.push(node1->right);
            } else if(!node1->right) {
                node1->right = node2->right;
            }
            if(node1->left && node2->left) {
                st.push(node2->left);
                st.push(node1->left);
            } else if(!node1->left) {
                node1->left = node2->left;
            }                        
        }
        return root1;
    }
};

层次遍历

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if(!root1)      return root2;
        if(!root2)      return root1;
        queue<TreeNode*> que;
        que.push(root1);
        que.push(root2);
        while(!que.empty()) {
            TreeNode* node1 = que.front();      que.pop();
            TreeNode* node2 = que.front();      que.pop();
            node1->val += node2->val;
            if(node1->left && node2->left) {
                que.push(node1->left);
                que.push(node2->left);
            } else if(!node1->left) {
                node1->left = node2->left;
            }
            if(node1->right && node2->right) {
                que.push(node1->right);
                que.push(node2->right);
            } else if(!node1->right) {
                node1->right = node2->right;
            }
        }
        return root1;
    }
};