题目地址(617. 合并二叉树)

https://leetcode-cn.com/problems/merge-two-binary-trees/

题目描述

  1. 给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
  3. 你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
  5. 示例 1:
  7. 输入: 
  8.     Tree 1                     Tree 2                  
  9.           1                         2                             
  10.          / \                       / \                            
  11.         3   2                     1   3                        
  12.        /                           \   \                      
  13.       5                             4   7                  
  14. 输出: 
  15. 合并后的树:
  16.          3
  17.         / \
  18.        4   5
  19.       / \   \ 
  20.      5   4   7
  23. 注意: 合并必须从两个树的根节点开始。

前置知识


公司

  • 暂无

思路

确定好单层逻辑就行
虽然是同时操作两颗树 但是他们的操作是同步的

关键点


代码

  • 语言支持：Java

Java Code:

  2. /**
  3.  * Definition for a binary tree node.
  4.  * public class TreeNode {
  5.  *     int val;
  6.  *     TreeNode left;
  7.  *     TreeNode right;
  8.  *     TreeNode() {}
  9.  *     TreeNode(int val) { this.val = val; }
  10.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  11.  *         this.val = val;
  12.  *         this.left = left;
  13.  *         this.right = right;
  14.  *     }
  15.  * }
  16.  */
  17. class Solution {
  18.         //1确定递归的返回值和参数 返回值是合并后的二叉树 参数是两个合并前的二叉树 所以直接用方法体就行
  19.         public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
  20.             //2 确定中止条件 如果左边null 右边有值 返回的是右边的 反之返回左边的 如果两边都为空也没关系 返回null就行
  21.             if (root1 == null) {
  22.                 return root2;
  23.             }
  24.             if (root2 == null) {
  25.                 return root1;
  26.             }
  27.             //3 每次递归的逻辑 如果不是上面的情况 就将两边的二叉树的值相加
  28.             TreeNode treeNode = new TreeNode(root1.val + root2.val);
  29.             treeNode.left = mergeTrees(root1.left, root2.left);
  30.             treeNode.right = mergeTrees(root1.right, root2.right);
  31.             return treeNode;
  32.         }
  33.     }

复杂度分析

令 n 为数组长度。

  • 时间复杂度：617. 合并二叉树 - 图1#card=math&code=O%28n%29&id=vGBEF)
  • 空间复杂度：617. 合并二叉树 - 图2#card=math&code=O%28n%29&id=VnOew)