二叉树 合并二叉树617

需求

给你两棵二叉树： root1 和 root2 。

想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。

返回合并后的二叉树。

**注意: **合并过程必须从两个树的根节点开始。

示例：1

合并二叉树

输入： root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
输出： [3,4,5,5,4,null,7]

leetcode题目链接

思路：

根据题目就是将两个二叉树进行合并，相同位置元素值进行相加后生成一个新的二叉树。
递归法：
递归法最简单的办法是使用前序遍历，获取中节点数据详见，在递归左右子节点数值相加。
层序遍历：
根据层进行遍历，利用其中一棵二叉树，作为返回值，将另一棵二叉树的值替换或者相加到当前二叉树。

/**
 * 617. 合并二叉树
 * 前序遍历
 */
public class MergeTrees617 {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 == null) return null;
        int roo1Val = 0;
        int root2Val = 0;
        if (root1 != null) roo1Val = root1.val;
        if (root2 != null) root2Val = root2.val;

        TreeNode node = new TreeNode(roo1Val + root2Val); // 中

        node.left = mergeTrees(
                root1 == null ? null : root1.left
                , root2 == null ? null : root2.left);// 左

        node.right = mergeTrees(
                root1 == null ? null : root1.right
                , root2 == null ? null : root2.right);// 右
        return node;
    }

    // 递归精简版本
    public TreeNode mergeTreesJj(TreeNode root1, TreeNode root2) {
        if (root1 == null) return root2;
        if (root2 == null) return root1;

        root1.val += root2.val;// 中
        root1.left = mergeTrees(root1.left, root2.left);// 左
        root1.right = mergeTrees(root1.right, root2.right);// 右
        return root1;
    }

    /**
     * 层序遍历
     * 这个题的关键在于怎么关联第二层数据
     * 利用其中一个二叉树，由第二个二叉树不起null位合并
     */
    public TreeNode mergeTreesGd(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()){
            int size = stack.size();
            while (size>0){// 这个while可以省略掉
                size -=2;
                TreeNode node1 = stack.pop();
                TreeNode node2 = stack.pop();
                node1.val+=node2.val;

                if(node1.left !=null && node2.left!=null){
                    stack.push(node2.left);
                    stack.push(node1.left);
                }else {
                    if(node1.left == null){
                        node1.left = node2.left;
                    }
                }
                if(node1.right!=null && node2.right!=null){
                    stack.push(node2.right);
                    stack.push(node1.right);

                }else {
                    if(node1.right == null){
                        node1.right=node2.right;
                    }
                }
            }
        }

        return root1;
    }
}

验证结果