加载中...
avatar

小陈的刷题日记(LeetCode九月每日一题)

LeetCode 617. 合并二叉树

题目描述

给定两个二叉树,想象当你将它们中的一个覆盖到另一个上时,两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠,那么将他们的值相加作为节点合并后的新值,否则不为 NULL 的节点将直接作为新二叉树的节点。

示例

输入: 
       Tree 1                     Tree 2
          1                         2
         / \                       / \
        3   2                     1   3
       /                           \   \
      5                             4   7
输出: 
合并后的树:
         3
        / \
       4   5
      / \   \ 
     5   4   7

解题思路

  1. 递归求解,结束条件是 t1结点 和 t2结点均为空的时候;

  2. 创建新的结点 root ,结点值为 t1结点 的值加上 t2结点 的值;

    1. t1结点为空时,结点值取 0
    2. t2同理。
    3. t1 和 t2 会同时为空,同时为空时已经达到递归结束条件返回了。
  3. 递归得到 root 的左子树和右子树;

    1. t1 为空时:

      1
      2
      root.left = mergeTrees(null, t2.left);
      root.right = mergeTrees(null, t2.right);
    2. t2 为空时:

      1
      2
      root.left = mergeTrees(t1.left, null);
      root.right = mergeTrees(t1.right, null);
    3. 均不为空时:

      1
      2
      root.left = mergeTrees(t1.left, t2.left);
      root.right = mergeTrees(t1.right, t2.right);
  4. 返回 root 即可。

AC

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
if (t1 == null && t2 == null) {
return null;
}

int val1 = t1 != null ? t1.val : 0;
int val2 = t2 != null ? t2.val : 0;
TreeNode root = new TreeNode(val1 + val2);
if (t1 == null) {
root.left = mergeTrees(null, t2.left);
root.right = mergeTrees(null, t2.right);
} else if (t2 == null) {
root.left = mergeTrees(t1.left, null);
root.right = mergeTrees(t1.right, null);
} else {
root.left = mergeTrees(t1.left, t2.left);
root.right = mergeTrees(t1.right, t2.right);
}
return root;
}
}
文章作者: 云开、见月明
文章链接: https://chenyunxin.cn/posts/1519021197.html
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 云开の博客
打赏
  • 微信
    微信
  • 支付寶
    支付寶

评论