leetcode-0617 合并二叉树
2024-08-28 10:46:08
题目地址https://leetcode-cn.com/problems/merge-two-binary-trees/
1.递归解法
递归的话我们首先需要递归的终止条件,对于本题而言,递归的终止条件是t1和t2递归到任意一方为null的情况,因为这种条件下,我们不需要继续合并下去,直接返回不为null那一方即可。整体递归的过程就比较简单了,分为三个步骤
- 求根节点本身
- 求根节点的左孩子节点
- 求根节点的右孩子节点
算法整体的时间复杂度为O(n) 空间复杂度为O(h) 其中h为二叉树的最大深度
var mergeTrees = function(t1, t2) {
if (t1 == null) return t2;
if (t2 == null) return t1;
const newRoot = new TreeNode(t1.val + t2.val);
newRoot.left = mergeTrees(t1.left, t2.left);
newRoot.right = mergeTrees(t1.right, t2.right);
return newRoot;
};
2.DFS
这种解法以t1为基准,直接在t1上面操作,最终将t1返回。时间复杂度O(n) 空间复杂度O(n)。
var mergeTrees = function(t1, t2) {
if (t1 === null) return t2;
if (t2 === null) return t1;
const stack = [[t1, t2]];
while (stack.length > 0) {
let [a, b] = stack.pop();
// 如果b为null,那无论a是否为空,a都不需要做出改变
if (b === null) continue;
a.val = a.val + b.val;
// 下面处理a和b的子节点
// 如果a的左孩子或者右孩子为null,那直接将其赋值为b的左孩子或者右孩子
if (a.left === null)
a.left = b.left;
else
stack.push([a.left, b.left])
if (a.right === null)
a.right = b.right
else
stack.push([a.right, b.right])
}
return t1;
};
3.BFS
这里基本上是和DFS一样,因为不需要在意遍历的顺序,只需要将每个节点都遍历到,因此也可以使用BFS。时间复杂度O(n) 空间复杂度O(n)。
class Solution {
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
Queue<TreeNode[]> queue = new LinkedList<>();
if (t1 == null) return t2;
if (t2 == null) return t1;
queue.offer(new TreeNode[]{t1, t2});
while (!queue.isEmpty()) {
TreeNode[] t = queue.poll();
if (t[1] == null) continue;
t[0].val += t[1].val;
if (t[0].left == null)
t[0].left = t[1].left;
else
queue.offer(new TreeNode[]{t[0].left, t[1].left});
if (t[0].right == null)
t[0].right = t[1].right;
else
queue.offer(new TreeNode[]{t[0].right, t[1].right});
}
return t1;
}
}
更多LeetCode题解和数据结构方面的内容,可以关注我的github,求个star~ ▄█▔▉●
最新文章
- 关于数组去重的几种方法-------javascript描述
- HttpClient 4.5.x 工具类设计与实现
- 演示一个VPD进行数据访问控制的示例
- LINQ使用
- iOS之沙盒机制和如何获取沙盒路径
- linux whereis which
- Sublime Text3 + Golang搭建开发环境
- iOS开发——NSArray中的字符串排序
- postgresql :: FATAL: could not write init file
- PAT 1039 到底买不买
- 泰克TDS1000B示波器使用说明
- python调用caffe实现预测
- _编程语言_C_C++_数据结构_struct
- Tomorrow Is A New Day
- pytts3语音合成遇到的中文问题
- 创造101:如果软件测试工程师组团出道,怎样才能站C位?!
- Gogland配置- 修改Go源代码tab值
- IntelliJ Idea各种技巧设置笔记和错误解决
- IIS和ASP.NET MVC 管道处理模型
- div模拟textarea在ios下不兼容的问题解决
热门文章
- win 7 系统过期处理办法
- 搭建生产级的Netty项目
- OpenCV-Python 傅里叶变换 | 三十
- 模型压缩一半,精度几乎无损,TensorFlow推出半精度浮点量化工具包,还有在线Demo...
- webpack配置打包vue文件
- .Net Core2.2 使用 AutoMapper进行实体转换
- coding++:error 阿里云 Redis集群一直Waiting for the cluster to join....存在以下隐患
- sql MySQL5.7 安装 centos docker
- RecyclerView 的简单使用
- Elasticsearch 核心术语概念