【树】C001_合并二叉树（dfs 递归 | 非递归）

一、题目描述

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.

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

二、题解

方法一：dfs 递归

• 以 t1 为基准，始终采取覆盖 t1 结点的策略。
• 两树同时前序遍历（即左路走到底，再走右路）。
• 遍历时，若两棵树的当前节点均不空，则将它们的值相加，并对它们的左孩子和右孩子进行递归合并。
• 有一棵树为空，则另一颗树作为结果。

/**
 * @date: 2/24/2020 8:20 PM
 * @Execution info：1ms，80.56%，11.53%
 */
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
  return dfs(t1, t2);
}
private TreeNode dfs(TreeNode t1, TreeNode t2) {
  if (t1 == null)
    return t2;
  if (t2 == null)
    return t1;
  //t1，t2都不空
  t1.val += t2.val;
  t1.left =  dfs(t1.left, t2.left);
  t1.right = dfs(t1.right, t2.right);
  return t1;
}

复杂度分析

• 时间复杂度：$O(min(N1, N2))$O(min(N1,N2))，
• 空间复杂度：$O(H)$O(H)，树高

---

方法二：dfs 非递归

• 联想一下递归 dfs，当两颗树的结点其中之一为空，则返回将不空的结点覆盖到空的结点。
• 递归时，我们同时让两棵树的左/右孩子进入递归，也就意味着，同时进栈。
• 只要右子树的结点不空，我们就有覆盖的机会；右子树结点空，没必要继续覆盖左子树。

/**
 * @date: 2/24/2020 9:04 PM
 * @Execution info：2ms，10.8%，%
 */
private TreeNode dfs(TreeNode t1, TreeNode t2) {

  if(t1 == null)
    return t2;
  Stack<TreeNode[]> stack = new Stack<>();
  stack.push(new TreeNode[]{t1, t2});

  while (!stack.isEmpty()) {
    TreeNode[] pair = stack.pop();
    if (pair[1] == null)
      continue;

    pair[0].val += pair[1].val;

    if (pair[0].left == null && pair[1].left != null) {
      pair[0].left = pair[1].left;
    } else {
      stack.push(new TreeNode[]{pair[0].left, pair[1].left});
    }
    if (pair[0].right == null && pair[1].right != null) {
      pair[0].right = pair[1].right;
    } else {
      stack.push(new TreeNode[]{pair[0].right, pair[1].right});
    }
  }
  return t1;
}

复杂度分析

• 时间复杂度：$O(min(N1, N2))$O(min(N1,N2))，
• 空间复杂度：$O(2N)$O(2N)，