Merging binary trees by recursion

617. Merge binary tree

The difficulty is simple

Here are two binary trees ： root1 and root2 .

Imagine , When you cover one tree over the other , Some nodes on the two trees will overlap （ And others don't ）. You need to merge these two trees into a new binary tree . The rule of consolidation is ： If two nodes overlap , Then add the values of the two nodes as the new values of the merged nodes ; otherwise , Not for null The node of will be the node of the new binary tree directly .

Returns the merged binary tree .

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

Ideas

For trees , Most of the problems can be solved by recursion , This is no exception

For each node , Judge whether the corresponding nodes of the current two trees are null,

• If it's all for null, Then return to null
• If one is for null, Then return to another tree
• If neither is null, Then the return value is the new tree of the sum of two nodes , Then continue to traverse the left and right child nodes of these two nodes

package cn.edu.xjtu.carlWay.tree.mergeTwoBinaryTree;

import cn.edu.xjtu.Util.TreeNode.TreeNode;

/** * 617.  Merge binary tree  *  Here are two binary trees ： root1  and  root2 . * <p> *  Imagine , When you cover one tree over the other , Some nodes on the two trees will overlap （ And others don't ）. You need to merge these two trees into a new binary tree . The rule of consolidation is ： If two nodes overlap , Then add the values of the two nodes as the new values of the merged nodes ; otherwise , Not for  null  The node of will be the node of the new binary tree directly . * <p> *  Returns the merged binary tree . * <p> *  Be careful :  The merge process must start at the root of both trees . * <p> * https://leetcode-cn.com/problems/merge-two-binary-trees/ */
public class Solution {
    
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
    
        //  Both nodes are null
        if (root1 == null && root2 == null) {
    
            return null;
        }
        //  One for null
        if (root1 == null) {
    
            return root2;
        }
        if (root2 == null) {
    
            return root1;
        }
        //  Neither is null
        TreeNode node = new TreeNode(root1.val + root2.val);
        node.left = mergeTrees(root1.left, root2.left);//  Continue processing the left child node 
        node.right = mergeTrees(root1.right, root2.right);//  Continue processing the right child node 

        return node;
    }
}