原题链接：

617. 合并二叉树

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

完成情况：

解题思路：

参考代码：

_617合并二叉树_使用队列迭代

package 代码随想录.树.二叉树;

import 代码随想录.树.TreeNode;

import java.util.Deque;
import java.util.LinkedList;

public class _617合并二叉树_使用队列迭代 {
    /**
     *
     * @param root1
     * @param root2
     * @return
     */
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null){
            return root2;
        }
        if (root2 == null){
            return root1;
        }
        Deque<TreeNode> myQueue = new LinkedList<TreeNode>();
        myQueue.offerLast(root1);
        myQueue.offerLast(root2);
        while (!myQueue.isEmpty()) {
            TreeNode node1 = myQueue.pollFirst();
            TreeNode node2 = myQueue.pollFirst();
            // 此时两个节点一定不为空，val相加
            node1.val = node1.val + node2.val;
            // 如果两棵树左节点都不为空，加入队列
            if (node1.left != null && node2.left != null){
                myQueue.offerLast(node1.left);
                myQueue.offerLast(node2.left);
            }
            // 如果两棵树右节点都不为空，加入队列
            if (node1.right != null && node2.right != null){
                myQueue.offerLast(node1.right);
                myQueue.offerLast(node2.right);
            }
            // 若node1的左节点为空，直接赋值
            if (node1.left == null && node2.left != null){
                node1.left = node2.left;
            }
            // 若node1的右节点为空，直接赋值
            if (node1.right == null && node2.right != null){
                node1.right = node2.right;
            }
        }
        return root1;
    }
}

_617合并二叉树_使用栈迭代

package 代码随想录.树.二叉树;

import 代码随想录.树.TreeNode;

import java.util.ArrayDeque;
import java.util.Deque;

public class _617合并二叉树_使用栈迭代 {
    /**
     *
     * @param root1
     * @param root2
     * @return
     */
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2){
        if(root1 == null){
            return root2;
        }
        if (root2 == null){
            return root1;
        }
        Deque<TreeNode> myStack = new ArrayDeque<TreeNode>();
        myStack.push(root2);
        myStack.push(root1);
        while (!myStack.isEmpty()){
            TreeNode node1 = myStack.pop();
            TreeNode node2 = myStack.pop();
            node1.val += node2.val;
            if (node2.right != null && node1.right != null){
                myStack.push(node2.right);
                myStack.push(node1.right);
            }else {
                if (node1.right == null){
                    node1.right = node2.right;
                }
            }
            if (node2.left != null && node1.left != null){
                myStack.push(node2.left);
                myStack.push(node1.left);
            }else {
                if (node1.left == null){
                    node1.left = node2.left;
                }
            }
        }
        return root1;
    }
}

错误经验吸取