LeetCode Merge Two Binary Trees

LeetCode 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.


上午又参加了一场LeetCode的比赛,第三题花了不少时间,第四题在11:06分AC了,但是比赛好像在11:00就结束了。。。无语,排名只有376。

这题要求把两棵二叉树合并,如果对应位置都有节点,则新节点的值等于两个老节点的值之和,否则等于有值的那个节点。

简单题,直接递归merge就好。代码如下:

class Solution {
public:
	TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
		if (t1 == NULL&&t2 == NULL)return NULL;
		if (t1 == NULL&&t2 != NULL)return t2;
		if (t1 != NULL&&t2 == NULL)return t1;
		TreeNode* left = mergeTrees(t1->left, t2->left);
		TreeNode* right = mergeTrees(t1->right, t2->right);
		TreeNode* root = new TreeNode(t1->val + t2->val);
		root->left = left;
		root->right = right;
		return root;
	}
};

本代码提交AC,用时49MS。

Leave a Reply

Your email address will not be published. Required fields are marked *