LEETCODE 617. 合并二叉树

LEETCODE 617. 合并二叉树

题目描述

给定两个二叉树,想象当你将它们中的一个覆盖到另一个上时,两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠,那么将他们的值相加作为节点合并后的新值,否则不为 NULL     的节点将直接作为新二叉树的节点。
示例 1:
输入:

	Tree 1                     Tree 2
          1                         2
         / \                       / \
        3   2                     1   3
       /                           \   \
      5                             4   7

输出:
合并后的树:

	     3
	    / \
	   4   5
	  / \   \
	 5   4   7

注意: 合并必须从两个树的根节点开始。

题目地址:
https://leetcode-cn.com/problems/merge-two-binary-trees/

递归实现

如果没有头绪的话,可以将这两颗树想象成是两个数组:

1 3 2 5
2 1 3 4 7

合并两个数组很直观,将数组2的值合并到数组1中,再返回数组1就可以了。
对于二叉树来说,如果我们像遍历数组那样,挨个遍历两颗二叉树中的每个节点,再把他们相加,那问题就比较容易解决了。

遍历二叉树很简单,用前序遍历就可以了,再依次把访问到的节点值相加,因为题目说的是一棵树覆盖另一棵树,所以我们不用再创建新的节点了,直接将树2合并到树1上再返回就可以了。
需要注意:这两颗树并不是长得完全一样,有的树可能有左节点,但有的树没有。对于这种情况,我们统一的都把他们挂到树1 上面就可以了,对于上面例子中的两颗树,合并起来的结果如下:

	     3
	    / \
	   4   5
	  / \   \
	 5   4   7

相当于树1少了一条腿,而树2有这条腿,那就把树2的拷贝过来。
总结下递归的条件:

  1. 终止条件:树1的节点为null,或者树2的节点为null
  2. 递归函数内:将两个树的节点相加后,再赋给树1的节点。再递归的执行两个树的左节点,递归执行两个树的右节点

动画演示如下:

时间复杂度:O(N)
空间复杂度:O(h),h是树的高度
java代码实现:

class Solution {
	public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
		return dfs(t1,t2);
	}
	
	TreeNode dfs(TreeNode r1, TreeNode r2) {
		// 如果 r1和r2中,只要有一个是null,函数就直接返回
		if(r1==null || r2==null) {
			return r1==null? r2 : r1;
		}
		//让r1的值 等于  r1和r2的值累加,再递归的计算两颗树的左节点、右节点
		r1.val += r2.val;
		r1.left = dfs(r1.left,r2.left);
		r1.right = dfs(r1.right,r2.right);
		return r1;
	}
}
                                                                                    

python代码实现:

class Solution(object):
	def mergeTrees(self, t1, t2):
		"""
		:type t1: TreeNode
		:type t2: TreeNode
		:rtype: TreeNode
		"""		
		def dfs(r1,r2):
			# 如果 r1和r2中,只要有一个是null,函数就直接返回
			if not (r1 and r2):
				return r1 if r1 else r2
			# 让r1的值 等于  r1和r2的值累加
			# 再递归的计算两颗树的左节点、右节点
			r1.val += r2.val
			r1.left = dfs(r1.left,r2.left)
			r1.right = dfs(r1.right,r2.right)
			return r1
		return dfs(t1,t2)
                                                                           

迭代实现

迭代实现用的是广度优先算法,广度优先就需要额外的数据结构来辅助了,我们可以借助栈或者队列来完成。
只要两颗树的左节点都不为null,就把将他们放入队列中;同理只要两棵树的右节点都不为null了,也将他们放入队列中。
然后我们不断的从队列中取出节点,把他们相加。
如果出现  树1的左节点为null,树2的左不为null,直接将树2的左节点赋给树1就可以了;同理如果树1的右节点为null,树2的右节点不为null,将树2的右节点赋给树1。
动画演示如下:

时间复杂度:O(N)
空间复杂度:O(N),对于满二叉树时,要保存所有的叶子节点,即N/2个节点。

java代码实现:

class Solution {
	public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
	        //如果 t1和t2中,只要有一个是null,函数就直接返回
		if(t1==null || t2==null) {
			return t1==null? t2 : t1;
		}
		java.util.LinkedList<TreeNode> queue = new java.util.LinkedList<TreeNode>();
		queue.add(t1);
		queue.add(t2);
		while(queue.size()>0) {
			TreeNode r1 = queue.remove();
			TreeNode r2 = queue.remove();
			r1.val += r2.val;
			//如果r1和r2的左子树都不为空,就放到队列中
			//如果r1的左子树为空,就把r2的左子树挂到r1的左子树上
			if(r1.left!=null && r2.left!=null){
				queue.add(r1.left);
				queue.add(r2.left);
			}
			else if(r1.left==null) {
				r1.left = r2.left;
			}
			//对于右子树也是一样的
			if(r1.right!=null && r2.right!=null) {
				queue.add(r1.right);
				queue.add(r2.right);
			}
			else if(r1.right==null) {
				r1.right = r2.right;
			}
		}
		return t1;
	}
}
                                                                                                  

python代码实现:

class Solution(object):
	def mergeTrees(self, t1, t2):
		"""
		:type t1: TreeNode
		:type t2: TreeNode
		:rtype: TreeNode
		"""	
	        # 如果 t1和t2中,只要有一个是null,函数就直接返回
		if not (t1 and t2):
			return t2 if not t1 else t1
		queue = [(t1,t2)]
		while queue:
			r1,r2 = queue.pop(0)
			r1.val += r2.val
			# 如果r1和r2的左子树都不为空,就放到队列中
			# 如果r1的左子树为空,就把r2的左子树挂到r1的左子树上
			if r1.left and r2.left:
				queue.append((r1.left,r2.left))
			elif not r1.left:
				r1.left = r2.left
			# 对于右子树也是一样的
			if r1.right and r2.right:
				queue.append((r1.right,r2.right))
			elif not r1.right:
				r1.right = r2.right
		return t1
                                                                               

(全文完)

13 次阅读

发表评论

电子邮件地址不会被公开。