刷题leetcode--617. Merge Two Binary Trees

港控/mmm° 2021-10-09 03:48 240阅读 0赞

617. Merge Two Binary Trees

Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.

You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.

Example 1:

Input: 
    	Tree 1                     Tree 2                  
              1                         2                             
             / \                       / \                            
            3   2                     1   3                        
           /                           \   \                      
          5                             4   7                  
    Output: 
    Merged tree:
    	     3
    	    / \
    	   4   5
    	  / \   \ 
    	 5   4   7

Note: The merging process must start from the root nodes of both trees.

题意：合并两个二叉树，两个都有值的地方数值相加，只有一个树有的保留这个树的值。

思路：二叉树，

(1)先判断，两个树是否为空，如果是都是空返回null；如果一个为空另一个不是空，保留其值创建新树;l两个都不是空，求和后放新结点。

(2)递归调用，root.left=mergeTrees(t1.left, t2.left)； root.right = mergeTrees(t1.right,t2.right);

程序1：

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
             // 写法1
             if(t1==null && t2==null){
                  return null;
             }
             else if(t1==null ){
                  return t2;
             }else if(t2==null)
                return t1;
             TreeNode root = new TreeNode(t1.val+t2.val);
             root.left =mergeTrees(t1 == null? null :t1.left, t2 == null? null :t2.left);
             root.right = mergeTrees(t1.right,t2.right);
             return root;
                            
        }
          
    }

程序2：

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
             //写法二 
             if(t1==null && t2 ==null) return null;
             int val= (t1==null?0:t1.val) +(t2==null?0:t2.val);
             TreeNode newNode = new TreeNode(val);
             newNode.left = mergeTrees(t1 == null ? null : t1.left, t2 == null ? null : t2.left);
             newNode.right = mergeTrees(t1 == null ? null : t1.right, t2 == null ? null : t2.right);
             return newNode;
            
        }
          
    }