2019-06-10.md

每日一题 - merge-two-binary-trees

信息卡片

• 时间：2019-06-10
• 题目链接：https://leetcode-cn.com/problems/merge-two-binary-trees/
• tag：tree Recursion

题目描述

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.

参考答案

递归

• 构造新tree的根节点
• 递归构造新tree根节点左子树
• 递归构造新tree根节点右子树

理解“树是一种递归的数据结构”

Time complexity : O(n) Space complexity : O(n)

参考代码

/*
 * @lc app=leetcode id=617 lang=javascript
 *
 * [617] Merge Two Binary Trees
 */
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} t1
 * @param {TreeNode} t2
 * @return {TreeNode}
 */
var mergeTrees = function(t1, t2) {
  // 递归，由于树是一种递归的数据结构，因此递归是符合直觉且比较简单的
  if (t1 === null) return t2;
  if (t2 === null) return t1;
  t1.val += t2.val;
  t1.left = mergeTrees(t1.left, t2.left);
  t1.right = mergeTrees(t1.right, t2.right);
  return t1;
};

其他优秀解答

迭代

层次遍历，利用数据结构是队列。

参考代码

class Solution2 {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) 
    {  
      //t2合并到t1上,t1必须存在,如果不存在就结束。
      if(t1 ==NULL)
      {
          return t2;
      }
     vector<TreeNode*> node(2);
     node[0]=t1;
     node[1]=t2;

     queue<vector<TreeNode*>> data;
     data.push(node); //第一次出队列的数据就是root节点.
     

     while(!data.empty())
     {
         //出队列操作
         vector<TreeNode*> temp=data.front();
         data.pop();

         TreeNode*pt1=temp[0];
         TreeNode*pt2=temp[1];
         if(pt2==NULL)
         {
            continue;//维持pt1结构不变
            
         }
          //pt1如果null 是不入队列的。
          pt1->val+=pt2->val; // 结构不变，只修改节点数值
          //
         if(pt1->left ==NULL)
         {
            pt1->left =pt2->left; //结构发生生变化，不能如队列。该节点遍历将结束。
         }else
         {
             node[0]=pt1->left;
             node[1]=pt2->left;
             data.push(node); //结构不变，可以入队列操作

         }
 
        if(pt1->right ==NULL)
         {
            pt1->right =pt2->right; //结构发生生变化，不能如队列。该节点遍历将结束。
         }else
         {
             node[0]=pt1->right;
             node[1]=pt2->right;
             data.push(node);

         }
     }
    
     return t1;
    }
};