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

作者:Hann?Yang 时间:2024-04-28 10:45:18 

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语言算法题解二叉树的拷贝、镜像和对称

来源:https://hannyang.blog.csdn.net/article/details/126556548

标签:go语言,二叉树,镜像,对称
0
投稿

猜你喜欢

  • Python类继承和多态原理解析

    2023-04-30 17:31:38
  • C#实现Excel表数据导入Sql Server数据库中的方法

    2024-01-19 01:19:01
  • 使用Python获取并处理IP的类型及格式方法

    2023-12-20 00:18:23
  • Python设计足球联赛赛程表程序的思路与简单实现示例

    2023-05-02 20:58:05
  • 轻轻松松学习JavaScript

    2024-06-07 15:51:08
  • 优化Oracle停机时间及数据库恢复

    2010-07-20 12:54:00
  • 基于JS实现简单滑块拼图游戏

    2024-04-17 09:52:33
  • JavaScript事件冒泡

    2009-12-28 13:21:00
  • python+requests+unittest API接口测试实例(详解)

    2021-10-14 13:15:08
  • CentOS 6.5下yum安装 MySQL-5.5全过程图文教程

    2024-01-20 03:03:12
  • 附加到SQL2012的数据库就不能再附加到低于SQL2012的数据库版本的解决方法

    2024-01-27 19:46:16
  • Python列表推导式的使用方法

    2023-05-10 07:01:46
  • Python中if语句的基本格式实例代码

    2023-12-02 14:31:20
  • JavaScript加密解密终级指南

    2008-01-03 12:25:00
  • Vue如何实现组件的源码解析

    2024-05-09 15:21:19
  • 对dataframe进行列相加,行相加的实例

    2023-07-24 16:57:59
  • Pytorch中实现CPU和GPU之间的切换的两种方法

    2021-08-21 07:24:18
  • Python 中制作偶数列表的方法

    2022-08-20 20:15:56
  • python实现打砖块游戏

    2023-11-09 21:27:15
  • js 实现的可折叠留言板(附源码下载)

    2024-04-22 13:07:49
  • asp之家 网络编程 m.aspxhome.com