程序员吧
首页 >编程 >正文

go语言算法题解二叉树的拷贝、镜像和对称

2023-01-14 12:13出处/作者：小冰整合编辑：@小冰
这篇文章主要为大家详细介绍了go语言算法题解二叉树的拷贝、镜像和对称，文中的示例代码讲解详细，感兴趣的小伙伴可以跟随小编一起学习一下

go语言算法题解二叉树的拷贝、镜像和对称

拷贝副本

复制一个二叉树副本，广度优先遍历同时设置两个队列，一个遍历一个复制创建。

func Copy(bt *biTree) *biTree {
	root := bt.Root
	if root == nil {
		return &biTree{}
	}
	node := &btNode{Data: root.Data}
	Queue1, Queue2 := []*btNode{root}, []*btNode{node}
	for len(Queue1) > 0 {
		p1, p2 := Queue1[0], Queue2[0]
		Queue1, Queue2 = Queue1[1:], Queue2[1:]
		if p1.Lchild != nil {
			Node := &btNode{Data: p1.Lchild.Data}
			p2.Lchild = Node
			Queue1 = append(Queue1, p1.Lchild)
			Queue2 = append(Queue2, Node)
		}
		if p1.Rchild != nil {
			Node := &btNode{Data: p1.Rchild.Data}
			p2.Rchild = Node
			Queue1 = append(Queue1, p1.Rchild)
			Queue2 = append(Queue2, Node)
		}
	}
	return &biTree{Root: node}
}

相同二叉树

递归法

func Equal(bt1, bt2 *btNode) bool {
	if bt1 == nil && bt2 == nil {
		return true
	} else if bt1 == nil || bt2 == nil {
		return false
	}
	if bt1.Data != bt2.Data {
		return false
	}
	return Equal(bt1.Lchild, bt2.Lchild) && Equal(bt1.Rchild, bt2.Rchild)
}
 
func (bt *biTree) Equal(bt2 *biTree) bool {
	return Equal(bt.Root, bt2.Root)
}

BFS

过程与复制副本类似，设置两个队列，同时遍历只要有一处不同即返回不相同。

func (bt *biTree) SameAs(bt2 *biTree) bool {
	root1, root2 := bt.Root, bt2.Root
	if root1 == nil && root2 == nil {
		return true
	} else if root1 == nil || root2 == nil {
		return false
	}
	Queue1, Queue2 := []*btNode{root1}, []*btNode{root2}
	p1, p2 := Queue1[0], Queue2[0]
	for len(Queue1) > 0 && len(Queue2) > 0 {
		p1, p2 = Queue1[0], Queue2[0]
		Queue1, Queue2 = Queue1[1:], Queue2[1:]
		if p1.Lchild != nil {
			if p2.Lchild == nil || p1.Lchild.Data != p2.Lchild.Data {
				return false
			}
			Queue1 = append(Queue1, p1.Lchild)
			Queue2 = append(Queue2, p2.Lchild)
		} else if p2.Lchild != nil {
			if p1.Lchild == nil || p1.Lchild.Data != p2.Lchild.Data {
				return false
			}
			Queue1 = append(Queue1, p1.Lchild)
			Queue2 = append(Queue2, p2.Lchild)
		}
		if p1.Rchild != nil {
			if p2.Rchild == nil || p1.Rchild.Data != p2.Rchild.Data {
				return false
			}
			Queue1 = append(Queue1, p1.Rchild)
			Queue2 = append(Queue2, p2.Rchild)
		} else if p2.Rchild != nil {
			if p1.Rchild == nil || p1.Rchild.Data != p2.Rchild.Data {
				return false
			}
			Queue1 = append(Queue1, p1.Rchild)
			Queue2 = append(Queue2, p2.Rchild)
		}
	}
	return true
}

go语言算法题解二叉树的拷贝、镜像和对称

镜像二叉树

生成一棵二叉树的镜像：

递归法

func (bt *btNode) InvertNodes() {
	if bt != nil {
		bt.Lchild.InvertNodes()
		bt.Rchild.InvertNodes()
		bt.Lchild, bt.Rchild = bt.Rchild, bt.Lchild
	}
}
 
func (bt *biTree) Mirror() {
	bt.Root.InvertNodes()
}

BFS

func Mirror(bt *biTree) *biTree {
	root := bt.Root
	if root == nil {
		return &biTree{}
	}
	node := &btNode{Data: root.Data}
	Queue1, Queue2 := []*btNode{root}, []*btNode{node}
	for len(Queue1) > 0 {
		p1, p2 := Queue1[0], Queue2[0]
		Queue1, Queue2 = Queue1[1:], Queue2[1:]
		if p1.Lchild != nil {
			Node := &btNode{Data: p1.Lchild.Data}
			p2.Rchild = Node
			Queue1 = append(Queue1, p1.Lchild)
			Queue2 = append(Queue2, Node)
		}
		if p1.Rchild != nil {
			Node := &btNode{Data: p1.Rchild.Data}
			p2.Lchild = Node
			Queue1 = append(Queue1, p1.Rchild)
			Queue2 = append(Queue2, Node)
		}
	}
	return &biTree{Root: node}
}

对称二叉树

方法一：判断左子树与右子树的反转是否相等

func (bt *biTree) IsSymmetry() bool {
	return Equal(bt.Root.Lchild, bt.Root.Rchild.InvertNodes())
}

方法二：判断自身与镜像是否相同

func (bt *biTree) IsSymmetry2() bool {
	bt2 := Mirror(bt)
	return bt.SameAs(bt2)
}

判断二棵二叉树是否互为镜像

方法一：生成其中一棵的镜像，判断镜像与另一棵是否相同

func (bt *biTree) IsMirror(bt2 *biTree) bool {
	return bt.SameAs(Mirror(bt2))
}

方法二：分别以此二棵树作左右子树生成一棵新树，判断新树是否左右对称

func (bt *biTree) IsMirror(bt2 *biTree) bool {
	root := &biTree{&btNode{1, bt.Root, bt2.Root}}
	return root.IsSymmetry()
}

包biTree函数汇总

至此，《数据结构：二叉树》系列（1~3）已累积了从创建、遍历等功能的20多个函数和方法，汇总如下：

/* The Package biTree
 * https://hannyang.blog.csdn.net/article/details/126556548
 *
 * based on Go program by Hann Yang,
 * modified on 2022/8/31.
 */
 
package biTree
 
type btNode struct {
	Data   interface{}
	Lchild *btNode
	Rchild *btNode
}
 
type biTree struct {
	Root *btNode
}
 
func Build(data interface{}) *biTree {
	var list []interface{}
	if data == nil {
		return &biTree{}
	}
	switch data.(type) {
	case []interface{}:
		list = append(list, data.([]interface{})...)
	default:
		list = append(list, data)
	}
	if len(list) == 0 {
		return &biTree{}
	}
	node := &btNode{Data: list[0]}
	list = list[1:]
	Queue := []*btNode{node}
	for len(list) > 0 {
		if len(Queue) == 0 {
			//panic("Given array can not build binary tree.")
			return &biTree{Root: node}
		}
		cur := Queue[0]
		val := list[0]
		Queue = Queue[1:]
		if val != nil {
			cur.Lchild = &btNode{Data: val}
			if cur.Lchild != nil {
				Queue = append(Queue, cur.Lchild)
			}
		}
		list = list[1:]
		if len(list) > 0 {
			val := list[0]
			if val != nil {
				cur.Rchild = &btNode{Data: val}
				if cur.Rchild != nil {
					Queue = append(Queue, cur.Rchild)
				}
			}
			list = list[1:]
		}
	}
	return &biTree{Root: node}
}
 
func Create(data interface{}) *biTree {
	var list []interface{}
	btree := &biTree{}
	switch data.(type) {
	case []interface{}:
		list = append(list, data.([]interface{})...)
	default:
		list = append(list, data)
	}
	if len(list) > 0 {
		btree.Root = &btNode{Data: list[0]}
		for _, data := range list[1:] {
			btree.AppendNode(data)
		}
	}
	return btree
}
 
func (bt *biTree) Append(data interface{}) {
	var list []interface{}
	switch data.(type) {
	case []interface{}:
		list = append(list, data.([]interface{})...)
	default:
		list = append(list, data)
	}
	if len(list) > 0 {
		for _, data := range list {
			bt.AppendNode(data)
		}
	}
}
 
func (bt *biTree) AppendNode(data interface{}) {
	root := bt.Root
	if root == nil {
		bt.Root = &btNode{Data: data}
		return
	}
	Queue := []*btNode{root}
	for len(Queue) > 0 {
		cur := Queue[0]
		Queue = Queue[1:]
		if cur.Lchild != nil {
			Queue = append(Queue, cur.Lchild)
		} else {
			cur.Lchild = &btNode{Data: data}
			return
		}
		if cur.Rchild != nil {
			Queue = append(Queue, cur.Rchild)
		} else {
			cur.Rchild = &btNode{Data: data}
			break
		}
	}
}
 
func (bt *biTree) Levelorder() []interface{} { //BFS
	var res []interface{}
	root := bt.Root
	if root == nil {
		return res
	}
	Queue := []*btNode{root}
	for len(Queue) > 0 {
		cur := Queue[0]
		Queue = Queue[1:]
		res = append(res, cur.Data)
		if cur.Lchild != nil {
			Queue = append(Queue, cur.Lchild)
		}
		if cur.Rchild != nil {
			Queue = append(Queue, cur.Rchild)
		}
	}
	return res
}
 
func (bt *biTree) BForder2D() [][]interface{} {
	var res [][]interface{}
	root := bt.Root
	if root == nil {
		return res
	}
	Queue := []*btNode{root}
	for len(Queue) > 0 {
		Nodes := []interface{}{}
		Levels := len(Queue)
		for Levels > 0 {
			cur := Queue[0]
			Queue = Queue[1:]
			Nodes = append(Nodes, cur.Data)
			Levels--
			if cur.Lchild != nil {
				Queue = append(Queue, cur.Lchild)
			}
			if cur.Rchild != nil {
				Queue = append(Queue, cur.Rchild)
			}
		}
		res = append(res, Nodes)
	}
	return res
}
 
func (bt *biTree) Preorder() []interface{} {
	var res []interface{}
	cur := bt.Root
	Stack := []*btNode{}
	for cur != nil || len(Stack) > 0 {
		for cur != nil {
			res = append(res, cur.Data)
			Stack = append(Stack, cur)
			cur = cur.Lchild
		}
		if len(Stack) > 0 {
			cur = Stack[len(Stack)-1]
			Stack = Stack[:len(Stack)-1]
			cur = cur.Rchild
		}
	}
	return res
}
 
func (bt *biTree) Inorder() []interface{} {
	var res []interface{}
	cur := bt.Root
	Stack := []*btNode{}
	for cur != nil || len(Stack) > 0 {
		for cur != nil {
			Stack = append(Stack, cur)
			cur = cur.Lchild
		}
		if len(Stack) > 0 {
			cur = Stack[len(Stack)-1]
			res = append(res, cur.Data)
			Stack = Stack[:len(Stack)-1]
			cur = cur.Rchild
		}
	}
	return res
}
 
func (bt *biTree) Postorder() []interface{} {
	var res []interface{}
	if bt.Root == nil {
		return res
	}
	cur, pre := &btNode{}, &btNode{}
	Stack := []*btNode{bt.Root}
	for len(Stack) > 0 {
		cur = Stack[len(Stack)-1]
		if cur.Lchild == nil && cur.Rchild == nil ||
			pre != nil && (pre == cur.Lchild || pre == cur.Rchild) {
			res = append(res, cur.Data)
			Stack = Stack[:len(Stack)-1]
			pre = cur
		} else {
			if cur.Rchild != nil {
				Stack = append(Stack, cur.Rchild)
			}
			if cur.Lchild != nil {
				Stack = append(Stack, cur.Lchild)
			}
		}
	}
	return res
}
 
func (bt *btNode) MaxDepth() int {
	if bt == nil {
		return 0
	}
	Lmax := bt.Lchild.MaxDepth()
	Rmax := bt.Rchild.MaxDepth()
	return 1 + Max(Lmax, Rmax)
}
 
func (bt *btNode) MinDepth() int {
	if bt == nil {
		return 0
	}
	Lmin := bt.Lchild.MinDepth()
	Rmin := bt.Rchild.MinDepth()
	return 1 + Min(Lmin, Rmin)
}
 
func (bt *biTree) Depth() int { //BFS
	res := 0
	root := bt.Root
	if root == nil {
		return res
	}
	Queue := []*btNode{root}
	for len(Queue) > 0 {
		Levels := len(Queue)
		for Levels > 0 {
			cur := Queue[0]
			Queue = Queue[1:]
			if cur.Lchild != nil {
				Queue = append(Queue, cur.Lchild)
			}
			if cur.Rchild != nil {
				Queue = append(Queue, cur.Rchild)
			}
			Levels--
		}
		res++
	}
	return res
}
 
func (bt *btNode) Degree() int {
	res := 0
	if bt.Lchild != nil {
		res++
	}
	if bt.Rchild != nil {
		res++
	}
	return res
}
 
func (bt *biTree) LeafNodeBFS() []interface{} {
	var res []interface{}
	root := bt.Root
	if root == nil {
		return res
	}
	Queue := []*btNode{root}
	for len(Queue) > 0 {
		cur := Queue[0]
		Queue = Queue[1:]
		//if cur.Lchild == nil && cur.Rchild == nil {
		if cur.Degree() == 0 {
			res = append(res, cur.Data)
		}
		if cur.Lchild != nil {
			Queue = append(Queue, cur.Lchild)
		}
		if cur.Rchild != nil {
			Queue = append(Queue, cur.Rchild)
		}
	}
	return res
}
 
func (bt *biTree) LeafNodeDFS() []interface{} {
	var res []interface{}
	cur := bt.Root
	Stack := []*btNode{}
	for cur != nil || len(Stack) > 0 {
		for cur != nil {
			//if cur.Lchild == nil && cur.Rchild == nil {
			if cur.Degree() == 0 {
				res = append(res, cur.Data)
			}
			Stack = append(Stack, cur)
			cur = cur.Lchild
		}
		if len(Stack) > 0 {
			cur = Stack[len(Stack)-1]
			Stack = Stack[:len(Stack)-1]
			cur = cur.Rchild
		}
	}
	return res
}
 
func (bt *btNode) InvertNodes() *btNode {
	if bt != nil {
		bt.Lchild.InvertNodes()
		bt.Rchild.InvertNodes()
		bt.Lchild, bt.Rchild = bt.Rchild, bt.Lchild
	}
	return bt
}
 
func (bt *biTree) Mirror() {
	bt.Root.InvertNodes()
}
 
func Copy(bt *biTree) *biTree {
	root := bt.Root
	if root == nil {
		return &biTree{}
	}
	node := &btNode{Data: root.Data}
	Queue1, Queue2 := []*btNode{root}, []*btNode{node}
	for len(Queue1) > 0 {
		p1, p2 := Queue1[0], Queue2[0]
		Queue1, Queue2 = Queue1[1:], Queue2[1:]
		if p1.Lchild != nil {
			Node := &btNode{Data: p1.Lchild.Data}
			p2.Lchild = Node
			Queue1 = append(Queue1, p1.Lchild)
			Queue2 = append(Queue2, Node)
		}
		if p1.Rchild != nil {
			Node := &btNode{Data: p1.Rchild.Data}
			p2.Rchild = Node
			Queue1 = append(Queue1, p1.Rchild)
			Queue2 = append(Queue2, Node)
		}
	}
	return &biTree{Root: node}
}
 
func Mirror(bt *biTree) *biTree {
	root := bt.Root
	if root == nil {
		return &biTree{}
	}
	node := &btNode{Data: root.Data}
	Queue1, Queue2 := []*btNode{root}, []*btNode{node}
	for len(Queue1) > 0 {
		p1, p2 := Queue1[0], Queue2[0]
		Queue1, Queue2 = Queue1[1:], Queue2[1:]
		if p1.Lchild != nil {
			Node := &btNode{Data: p1.Lchild.Data}
			p2.Rchild = Node
			Queue1 = append(Queue1, p1.Lchild)
			Queue2 = append(Queue2, Node)
		}
		if p1.Rchild != nil {
			Node := &btNode{Data: p1.Rchild.Data}
			p2.Lchild = Node
			Queue1 = append(Queue1, p1.Rchild)
			Queue2 = append(Queue2, Node)
		}
	}
	return &biTree{Root: node}
}
 
func Max(L, R int) int {
	if L > R {
		return L
	} else {
		return R
	}
}
 
func Min(L, R int) int {
	if L < R {
		return L
	} else {
		return R
	}
}
 
func Equal(bt1, bt2 *btNode) bool {
	if bt1 == nil && bt2 == nil {
		return true
	} else if bt1 == nil || bt2 == nil {
		return false
	}
	if bt1.Data != bt2.Data {
		return false
	}
	return Equal(bt1.Lchild, bt2.Lchild) && Equal(bt1.Rchild, bt2.Rchild)
}
 
func (bt *biTree) Equal(bt2 *biTree) bool {
	return Equal(bt.Root, bt2.Root)
}
 
func (bt *biTree) SameAs(bt2 *biTree) bool {
	root1, root2 := bt.Root, bt2.Root
	if root1 == nil && root2 == nil {
		return true
	} else if root1 == nil || root2 == nil {
		return false
	}
	Queue1, Queue2 := []*btNode{root1}, []*btNode{root2}
	p1, p2 := Queue1[0], Queue2[0]
	for len(Queue1) > 0 && len(Queue2) > 0 {
		p1, p2 = Queue1[0], Queue2[0]
		Queue1, Queue2 = Queue1[1:], Queue2[1:]
		if p1.Lchild != nil {
			if p2.Lchild == nil || p1.Lchild.Data != p2.Lchild.Data {
				return false
			}
			Queue1 = append(Queue1, p1.Lchild)
			Queue2 = append(Queue2, p2.Lchild)
		} else if p2.Lchild != nil {
			if p1.Lchild == nil || p1.Lchild.Data != p2.Lchild.Data {
				return false
			}
			Queue1 = append(Queue1, p1.Lchild)
			Queue2 = append(Queue2, p2.Lchild)
		}
		if p1.Rchild != nil {
			if p2.Rchild == nil || p1.Rchild.Data != p2.Rchild.Data {
				return false
			}
			Queue1 = append(Queue1, p1.Rchild)
			Queue2 = append(Queue2, p2.Rchild)
		} else if p2.Rchild != nil {
			if p1.Rchild == nil || p1.Rchild.Data != p2.Rchild.Data {
				return false
			}
			Queue1 = append(Queue1, p1.Rchild)
			Queue2 = append(Queue2, p2.Rchild)
		}
	}
	return true
}
 
func (bt *biTree) MirrorOf(bt2 *biTree) bool {
	return bt.SameAs(Mirror(bt2))
}
 
func (bt *biTree) IsMirror(bt2 *biTree) bool {
	root := &biTree{&btNode{1, bt.Root, bt2.Root}}
	return root.IsSymmetry()
}
 
func (bt *biTree) IsSymmetry() bool {
	return Equal(bt.Root.Lchild, bt.Root.Rchild.InvertNodes())
}
 
func (bt *biTree) IsSymmetry2() bool {
	bt2 := Mirror(bt)
	return bt.SameAs(bt2)
}

另外：从leetcode题目中整理了50多个与二叉树相关的题目，对照看看还有多少没刷过？

go语言算法题解二叉树的拷贝、镜像和对称

到此这篇关于go语言算法题解二叉树的拷贝、镜像和对称的文章就介绍到这了,更多相关go之二叉树的拷贝、镜像和对称内容请搜索脚本之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持脚本之家！

Python实现新年愿望代码雨效果
golang中new与make的区别讲解

网友评论

登录 注册
iCMS
验证码 换一张
取 消
暂无评论...
24小时内最火资讯
  1. 1Python之列表推导式最全汇总(上篇)
  2. 2Win11安装VMware Workstation Pro,Centos,Xshell,Xftp图文教程(Linux学习必备)
  3. 3springboot使用mybatis开启事务回滚
  4. 4windows2003 的安装及安装过程遇到的问题小结
  5. 5git可视化工具Sourcetree使用全攻略(git冲突解决)
  6. 6django+vue项目搭建实现前后端通信
  7. 7Redis 分片集群的实现
  8. 8springboot使用mybatis开启事务回滚
  9. 9GPU版本安装Pytorch的最新方法步骤
  10. 10Win11安装VMware Workstation Pro,Centos,Xshell,Xftp图文教程(Linux学习必备)
三日内热门评论文章
  1. 1 Win11安装VMware Workstation Pro,Centos,Xshell,Xftp图文教程(Linux学习必备)
  2. 2 Redis处理高并发之布隆过滤器详解
  3. 3 一文带你了解MySQL字符集和比较规则
  4. 4 MySQL常见内置函数以及其使用教程
  5. 5 解决Spring Cloud feign GET请求无法用实体传参的问题
  6. 6 Feign调用中的两种Header传参方式小结
  7. 7 yocto queue微型队列数据结构源码解读
  8. 8 Idea中如何查看SpringSecurity各Filter信息
  9. 9 arrify 转数组实现示例源码解析
  10. 10 Css-In-Js实现classNames库源码解读
精彩图赏
热门视频
月度热门文章
  1. 264
    全网最强下载神器IDM使用教程之利用IDM加速下载百度网盘大文件的方法
    ·
  2. 218
    MySQL如何查看正在运行的SQL详解
    ·
  3. 198
    关于yolov8训练的一些改动及注意事项
    ·
  4. 150
    chatgpt国内镜像 pycharm idea插件使用详解
    ·
  5. 149
    VS Code里使用Debugger for Unity插件调试的方法(2023最新版)
    ·
  6. 125
    全网最强下载神器IDM使用教程之利用IDM加速下载百度网盘大文件的方法
    ·
  7. 117
    JavaWeb day5 Tomcat配置及idea创建Maven-Tomcat项目
    ·
  8. 103
    buildcheck包报错问题排查解决
    ·
  9. 97
    vscode远程开发使用SSH远程连接服务器的方法「内网穿透」
    ·
  10. 96
    全网最强下载神器IDM使用教程之利用IDM加速下载百度网盘大文件的方法
    ·
关键词

为您推荐
  • 相关阅读
  • 业界资讯
  • 手机通讯
  • 电脑办公
  • 新奇数码
  • 软件游戏
  • 科学探索
用户反馈 返回首页 相关阅读 参与讨论 回到顶部

程序员吧感受编程的乐趣

法律声明：本站内容均为网友上传，网站举办方负责审核和监督，如存在版权或非法内容，欢迎举报，我们将尽快予以删除。

Copyright © 2022 程序员吧. All rights reserved. Powered by ITBeta V7.0.16