Leetcode 617 Merge Two Binary Trees 二叉树
2024-08-30 21:32:50
题意:
给定两棵树，将两棵树合并成一颗树
输入
Tree 1 Tree 2
1 2
/ \ / \
3 2 1 3
/ \ \
5 4 7
输出
合并的树
3
/ \
4 5
/ \ \
5 4 7 方法1不需要提供额外内存，但是时间居然很长
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func mergeTrees(t1 *TreeNode, t2 *TreeNode) *TreeNode {
if t1 == nil && t2 == nil{
return nil
}
if t1 != nil && t2 == nil{
return t1
}
if t1 == nil && t2 != nil{
return t2
}
if t1 != nil && t2 != nil{
t1.Val += t2.Val
t1.Left = mergeTrees(t1.Left, t2.Left);
t1.Right = mergeTrees(t1.Right, t2.Right);
}
return t1;
}
方法2需要提供额外内存，但是时间居然比方法1少，简直不可思议
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func newTreeNode() *TreeNode{
return &TreeNode{
}
} func dfs(m **TreeNode, t *TreeNode){ if t == nil {
return ;
} if (*m) == nil{
(*m) = newTreeNode()
} (*m).Val += t.Val
dfs(&((*m).Left), t.Left)
dfs(&((*m).Right), t.Right) } func mergeTrees(t1 *TreeNode, t2 *TreeNode) *TreeNode {
if t1 == nil && t2 == nil {
return nil
} m := newTreeNode() dfs(&m, t1);
dfs(&m, t2); return m;
}
最新文章
- Effective java笔记（八），异常
- Struts2理解--动态方法和method属性及通配符_默认Action
- 关于Servlet手动配置web.xml部分代码
- uva oj 567 - Risk(Floyd算法)
- （编辑器）Jquery-EasyUI集合Kindeditor编辑器
- rpc rmi http
- gulp.spritesmith修改px为rem单位
- Linux查看端口使用状态及启动
- LA 2038
- linux/shell sort命令
- asp.net中Get请求和Post请求
- Fragment的生命周期和Activity之间的通信以及使用
- 使用Javascript限制文本框只允许输入数字
- zepto源码研究 - zepto.js - 6(模板方法)
- 莫比乌斯反演题目泛做（为了对应smz的课件）
- jquery与ajax的应用
- 移动小bug
- MFC实现为窗体添加的背景图片
- SpringMVC中的异常处理
- J2EE_Maven_POM文件配置的详解（转）