Leetcode brush questions: binary tree 19 (merge binary tree)

617. Merge binary tree

Force button topic link

Given two binary trees , Imagine when you overlay one of them on the other , Some nodes of two binary trees will overlap .

You need to merge them into a new binary tree . The rule for merging is if two nodes overlap , Then add their values as the new values after node merging , Otherwise, no NULL The node of will be the node of the new binary tree directly .

Example 1:

Be careful : The merge must start at the root of both trees .

Based on one of the trees , Recursively traverse two trees at the same time , Each time, judge whether the current node exists in the non benchmark tree , Then add , non-existent , Then skip , The current node does not exist , Exist in non benchmark tree , Then add this node with the passed parent node , Remember to mark which tree it is .

package com.programmercarl.tree;

import com.programmercarl.util.GenerateTreeNode;

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

/** * @ClassName MergeTrees * @Descriotion TODO * @Author nitaotao * @Date 2022/7/5 18:02 * @Version 1.0 **/
public class MergeTrees {
    

    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
    
        if (root1 == null && root2 != null) {
    
            return root2;
        }
        if (root1 != null && root2 == null) {
    
            return root1;
        }
        if (root1 == null && root2 == null) {
    
            return null;
        }
        merge(root1, root2, false,null);
        return root1;
    }

    public void merge(TreeNode root1, TreeNode root2, boolean isLeft,TreeNode parent) {
    
        if (root1 == null && root2 == null) {
    
            return;
        }
        //  Based on the first tree 
        if (root1 != null && root2 != null) {
    
            root1.val = root1.val + root2.val;
        }

        if (root1 == null && root2 != null) {
    
            // If  1  No, ,2  Yes 
            if (isLeft) {
    
                parent.left = root2;
                return;
            } else {
    
                parent.right = root2;
                return;
            }
        }
        // If  1  Yes  , 2  No,   Do not change 
        if (root1 != null && root2 == null) {
    
            return;
        }
        merge(root1.left, root2.left, true,root1);
        merge(root1.right, root2.right, false,root1);
    }

    public static void main(String[] args) {
    
        new MergeTrees().mergeTrees(
                GenerateTreeNode.generateTreeNode("[9,-1,null,-2,0,-4,null,null,8,-5,-3,6,null,null,null,null,null,null,7]")
                ,
                GenerateTreeNode.generateTreeNode("[-1,-2,0,null,null,null,8,6,null,null,7]")
        );
    }

}

Let's take a look at the big guy's code

   //  recursive 
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
    
        if (root1 == null) return root2;
        if (root2 == null) return root1;

        TreeNode newRoot = new TreeNode(root1.val + root2.val);
        newRoot.left = mergeTrees(root1.left,root2.left);
        newRoot.right = mergeTrees(root1.right,root2.right);
        return newRoot;
    }