「LeetCode」617-合并二叉树⚡️

简介: 「LeetCode」617-合并二叉树⚡️

image.png

前言🌧️


算法,对前端人来说陌生又熟悉,很多时候我们都不会像后端工程师一样重视这项能力。但事实上,算法对每一个程序员来说,都有着不可撼动的地位。


因为开发的过程就是把实际问题转换成计算机可识别的指令,也就是《数据结构》里说的,「设计出数据结构,在施加以算法就行了」。


编写指令的好坏,会直接影响到程序的性能优劣,而指令又由数据结构和算法组成,所以数据结构和算法的设计基本上决定了最终程序的好坏


题目🦀


617. 合并二叉树


难度简单


给你两棵二叉树: root1root2


想象一下,当你将其中一棵覆盖到另一棵之上时,两棵树上的一些节点将会重叠(而另一些不会)。你需要将这两棵树合并成一棵新二叉树。合并的规则是:如果两个节点重叠,那么将这两个节点的值相加作为合并后节点的新值;否则,不为 null 的节点将直接作为新二叉树的节点。


返回合并后的二叉树。


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


示例 1:


image.png



输入:root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
输出:[3,4,5,5,4,null,7]

示例 2:


输入:root1 = [1], root2 = [1,2]
输出:[2,2]

提示:

  • 两棵树中的节点数目在范围 [0, 2000]
  • -104 <= Node.val <= 104


解题思路🌵


  • 采用前序遍历解决此题
  • 需要注意的是传入的参数,以及边界条件的处理
  • 当左结点为空时,返回右结点
  • 当右结点为空时,返回左结点
  • 当都不会空时,创建新结点,将左右结点值相加并赋值给新结点
  • 再进行递归调用


解题步骤🐂


  • 处理边界条件 root1为空 返回root2
  • 处理边界条件 root2为空 返回root1
  • 都不为空,创建新结点
  • 再此递归调用得到 treeNode.left
  • 再此递归调用得到 treeNode.right


源码🔥


/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root1
 * @param {TreeNode} root2
 * @return {TreeNode}
 */
var mergeTrees = function(root1, root2) {
    if(!root1){
        return root2
    }
     if(!root2){
        return root1
    }
    const treeNode = new TreeNode(root1.val+root2.val)
    treeNode.left = mergeTrees(root1.left,root2.left)
    treeNode.right = mergeTrees(root1.right,root2.right)
    return treeNode
};

时间复杂度:O(n)


空间复杂度:O(n)


结束语🌞


image.png


那么鱼鱼的LeetCode算法篇的「LeetCode」617-合并二叉树⚡️就结束了,算法这个东西没有捷径,只能多写多练,多总结,文章的目的其实很简单,就是督促自己去完成算法练习并总结和输出,菜不菜不重要,但是热爱🔥,喜欢大家能够喜欢我的短文,也希望通过文章认识更多志同道合的朋友,如果你也喜欢折腾,欢迎加我好友,一起沙雕,一起进步


相关文章
|
3天前
leetcode代码记录(二叉树的所有路径
leetcode代码记录(二叉树的所有路径
8 0
|
4天前
leetcode代码记录(对称二叉树 中序遍历+回文串 为什么不行
leetcode代码记录(对称二叉树 中序遍历+回文串 为什么不行
7 0
|
4天前
leetcode代码记录(二叉树的最小深度
leetcode代码记录(二叉树的最小深度
8 0
|
4天前
leetcode代码记录(二叉树的最大深度
leetcode代码记录(二叉树的最大深度
6 0
|
4天前
leetcode代码记录(翻转二叉树
leetcode代码记录(翻转二叉树
5 0
|
4天前
leetcode代码记录(二叉树的层序遍历
leetcode代码记录(二叉树的层序遍历
6 0
|
4天前
|
算法
leetcode代码记录(二叉树递归遍历
leetcode代码记录(二叉树递归遍历
7 0
|
18天前
[leetcode~dfs]1261. 在受污染的二叉树中查找元素
[leetcode~dfs]1261. 在受污染的二叉树中查找元素
[leetcode~dfs]1261. 在受污染的二叉树中查找元素
|
25天前
|
算法 API DataX
二叉树(下)+Leetcode每日一题——“数据结构与算法”“对称二叉树”“另一棵树的子树”“二叉树的前中后序遍历”
二叉树(下)+Leetcode每日一题——“数据结构与算法”“对称二叉树”“另一棵树的子树”“二叉树的前中后序遍历”
|
25天前
|
算法 DataX
二叉树(中)+Leetcode每日一题——“数据结构与算法”“剑指Offer55-I. 二叉树的深度”“100.相同的树”“965.单值二叉树”
二叉树(中)+Leetcode每日一题——“数据结构与算法”“剑指Offer55-I. 二叉树的深度”“100.相同的树”“965.单值二叉树”