617. 合并二叉树

先序递归

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        //先序递归
        if(root1 == null ) return root2;
        if(root2 == null ) 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.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        //中序
        if(root1 == null ) return root2;
        if(root2 == null ) return root1;
        root1.left = mergeTrees(root1.left,root2.left);
        root1.val += root2.val;
        root1.right = mergeTrees(root1.right,root2.right);
        return root1;
    }
}

后续递归

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        //后序
        if(root1 == null ) return root2;
        if(root2 == null ) return root1;
        root1.left = mergeTrees(root1.left,root2.left);
        root1.right = mergeTrees(root1.right,root2.right);
        root1.val += root2.val;
        return root1;
    }
}

递归不改变原树

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if(root1 == null ) return root2;
        if(root2 == null ) return root1;
        // 重新定义新的节点，不修改原有两个树的结构
        TreeNode root = new TreeNode(root1.val + root2.val);
        root.left = mergeTrees(root1.left,root2.left);
        root.right = mergeTrees(root1.right,root2.right);
        return root;
    }
}

栈（先序）

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        // 使用栈迭代(先序)
        if(root1 == null ) return root2;
        if(root2 == null ) return root1;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root2);
        stack.push(root1);
        while(! stack.isEmpty() ) {
            TreeNode node1 = stack.pop();
            TreeNode node2 = stack.pop();
            node1.val += node2.val;
            if(node2.right != null && node1.right != null ) {
                stack.push(node2.right);
                stack.push(node1.right);
            } else if(node1.right == null ) {
                node1.right = node2.right;
            }
            if(node2.left != null && node1.left != null ) {
                stack.push(node2.left);
                stack.push(node1.left);
            } else if(node1.left == null ) {
                node1.left = node2.left;
            }
        }
        return root1;
    }
}

队列

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if(root1 == null ) return root2;
        if(root2 == null ) return root1;
        Queue<TreeNode> que = new LinkedList<>();
        que.add(root1);
        que.add(root2);
        while (! que.isEmpty() ) {
            TreeNode node1 = que.poll();
            TreeNode node2 = que.poll();
            node1.val += node2.val;
            if(node1.left != null && node2.left != null ) {
                que.add(node1.left);
                que.add(node2.left);
            } else if(node1.left == null ) {
                node1.left = node2.left;
            }
            if(node1.right != null && node2.right != null ) {
                que.add(node1.right);
                que.add(node2.right);
            } else if(node1.right == null ) {
                node1.right = node2.right;
            }
        }
        return root1;
    }
}