LeetCode - Easy - 617. Merge Two Binary Trees

Topic

• Tree

Description

https://leetcode.com/problems/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.

Analysis

方法一：递归法。

方法二：迭代法。

方法三：别人写的递归法。发现自己没有审清题目。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. 两树都有的才新建一个节点，否则，能复用的就复用。

Submission

import java.util.LinkedList;

import com.lun.util.BinaryTree.TreeNode;

public class MergeTwoBinaryTrees {

	// 方法一：递归法
	public TreeNode mergeTrees1(TreeNode t1, TreeNode t2) {
		if (t1 == null && t2 == null) {
			return null;
		} else {
			TreeNode node = new TreeNode((t1 == null ? 0 : t1.val) + //
					(t2 == null ? 0 : t2.val));
			node.left = mergeTrees1(t1 == null ? null : t1.left, //
					t2 == null ? null : t2.left);
			node.right = mergeTrees1(t1 == null ? null : t1.right, //
					t2 == null ? null : t2.right);
			return node;
		}
	}

	// 方法二：迭代法
	public TreeNode mergeTrees2(TreeNode t1, TreeNode t2) {
		TreeNode result = null;

		if (t1 == null && t2 == null) {
			return null;
		} else {
			result = new TreeNode((t1 == null ? 0 : t1.val) + (t2 == null ? 0 : t2.val));
		}

		LinkedList<TreeNode[]> stack = new LinkedList<>();
		stack.push(new TreeNode[] { t1, t2, result });

		while (!stack.isEmpty()) {
			TreeNode[] nodes = stack.pop();
			TreeNode p1 = nodes[0], p2 = nodes[1], p3 = nodes[2];

			boolean p1AndItsLeftExised = p1 != null && p1.left != null;
			boolean p2AndItsLeftExised = p2 != null && p2.left != null;
			boolean p1AndItsRightExised = p1 != null && p1.right != null;
			boolean p2AndItsRightExised = p2 != null && p2.right != null;

			if (p1AndItsLeftExised || p2AndItsLeftExised) {
				int p1LeftValue = p1AndItsLeftExised ? p1.left.val : 0;
				int p2LeftValue = p2AndItsLeftExised ? p2.left.val : 0;
				p3.left = new TreeNode(p1LeftValue + p2LeftValue);
				stack.push(new TreeNode[] { p1AndItsLeftExised ? p1.left : null, //
						p2AndItsLeftExised ? p2.left : null, p3.left });
			}

			if (p1AndItsRightExised || p2AndItsRightExised) {
				int p1RightValue = p1AndItsRightExised ? p1.right.val : 0;
				int p2RightValue = p2AndItsRightExised ? p2.right.val : 0;
				p3.right = new TreeNode(p1RightValue + p2RightValue);
				stack.push(new TreeNode[] { p1AndItsRightExised ? p1.right : null, //
						p2AndItsRightExised ? p2.right : null, p3.right });
			}
		}

		return result;
	}

	// 方法三:别人写的递归法
	public TreeNode mergeTrees3(TreeNode t1, TreeNode t2) {
		if (t1 == null) {
			return t2;
		}
		if (t2 == null) {
			return t1;
		}
		TreeNode m = new TreeNode(t1.val + t2.val);
		m.left = mergeTrees3(t1.left, t2.left);
		m.right = mergeTrees3(t1.right, t2.right);

		return m;
	}
}
           

Test

import static org.junit.Assert.*;
import org.junit.Test;

import com.lun.util.BinaryTree;
import com.lun.util.BinaryTree.TreeNode;

public class MergeTwoBinaryTreesTest {


	@Test
	public void test1() {

		MergeTwoBinaryTrees obj = new MergeTwoBinaryTrees();
		TreeNode[] trees = makeTrees();
		TreeNode result = obj.mergeTrees1(trees[0], trees[1]);
		
		assertTrue(BinaryTree.equals(trees[2], result));
	}
	
	@Test
	public void test2() {
		
		MergeTwoBinaryTrees obj = new MergeTwoBinaryTrees();
		TreeNode[] trees = makeTrees();
		TreeNode result = obj.mergeTrees2(trees[0], trees[1]);
		
		assertTrue(BinaryTree.equals(trees[2], result));
	}
	
	@Test
	public void test3() {
		
		MergeTwoBinaryTrees obj = new MergeTwoBinaryTrees();
		TreeNode[] trees = makeTrees();
		TreeNode result = obj.mergeTrees2(trees[0], trees[1]);
		
		assertTrue(BinaryTree.equals(trees[2], result));
	}
	
	private TreeNode[] makeTrees() {
		TreeNode root1 = new TreeNode(1);
		
		root1.left = new TreeNode(3);
		root1.right = new TreeNode(2);
		
		root1.left.left = new TreeNode(5);
		
		//---
		
		TreeNode root2 = new TreeNode(2);
		root2.left = new TreeNode(1);
		root2.right = new TreeNode(3);
		
		root2.left.right = new TreeNode(4);
		root2.right.right = new TreeNode(7);
		
		//---
		
		TreeNode expected = new TreeNode(3);
		expected.left = new TreeNode(4);
		expected.right = new TreeNode(5);
		
		expected.left.left = new TreeNode(5);
		expected.left.right = new TreeNode(4);
		
		expected.right.right = new TreeNode(7);
		
		return new TreeNode[]{root1, root2, expected};
	}
}