go语言|数据结构:二叉树(3)拷贝、镜像和对称

简介: go语言|数据结构:二叉树(3)拷贝、镜像和对称

image.png




拷贝副本


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

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
}



9c495ad7216d4b29b03b6019caa91e1c.png


镜像二叉树

生成一棵二叉树的镜像:



递归法

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}
}


对称二叉树


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

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


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

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




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


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

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



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

 

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多个与二叉树相关的题目,对照看看还有多少没刷过?


eab7af180bab484f9f904c141f504fc1.png


预告:下一集准备刷二叉树路径的题目.……




目录
相关文章
|
10天前
|
算法 安全 Go
Go语言中的加密和解密是如何实现的?
Go语言通过标准库中的`crypto`包提供丰富的加密和解密功能,包括对称加密(如AES)、非对称加密(如RSA、ECDSA)及散列函数(如SHA256)。`encoding/base64`包则用于Base64编码与解码。开发者可根据需求选择合适的算法和密钥,使用这些包进行加密操作。示例代码展示了如何使用`crypto/aes`包实现对称加密。加密和解密操作涉及敏感数据处理,需格外注意安全性。
33 14
|
10天前
|
Go 数据库
Go语言中的包(package)是如何组织的?
在Go语言中,包是代码组织和管理的基本单元,用于集合相关函数、类型和变量,便于复用和维护。包通过目录结构、文件命名、初始化函数(`init`)及导出规则来管理命名空间和依赖关系。合理的包组织能提高代码的可读性、可维护性和可复用性,减少耦合度。例如,`stringutils`包提供字符串处理函数,主程序导入使用这些函数,使代码结构清晰易懂。
50 11
|
10天前
|
存储 安全 Go
Go语言中的map数据结构是如何实现的?
Go 语言中的 `map` 是基于哈希表实现的键值对数据结构,支持快速查找、插入和删除操作。其原理涉及哈希函数、桶(Bucket)、动态扩容和哈希冲突处理等关键机制,平均时间复杂度为 O(1)。为了确保线程安全,Go 提供了 `sync.Map` 类型,通过分段锁实现并发访问的安全性。示例代码展示了如何使用自定义结构体和切片模拟 `map` 功能,以及如何使用 `sync.Map` 进行线程安全的操作。
|
15天前
|
监控 安全 算法
深度剖析核心科技:Go 语言赋能局域网管理监控软件进阶之旅
在局域网管理监控中,跳表作为一种高效的数据结构,能显著提升流量索引和查询效率。基于Go语言的跳表实现,通过随机化索引层生成、插入和搜索功能,在高并发场景下展现卓越性能。跳表将查询时间复杂度优化至O(log n),助力实时监控异常流量,保障网络安全与稳定。示例代码展示了其在实际应用中的精妙之处。
36 9
|
30天前
|
存储 监控 算法
员工上网行为监控中的Go语言算法:布隆过滤器的应用
在信息化高速发展的时代,企业上网行为监管至关重要。布隆过滤器作为一种高效、节省空间的概率性数据结构,适用于大规模URL查询与匹配,是实现精准上网行为管理的理想选择。本文探讨了布隆过滤器的原理及其优缺点,并展示了如何使用Go语言实现该算法,以提升企业网络管理效率和安全性。尽管存在误报等局限性,但合理配置下,布隆过滤器为企业提供了经济有效的解决方案。
79 8
员工上网行为监控中的Go语言算法:布隆过滤器的应用
|
1月前
|
存储 Go 索引
go语言中数组和切片
go语言中数组和切片
46 7
|
1月前
|
Go 开发工具
百炼-千问模型通过openai接口构建assistant 等 go语言
由于阿里百炼平台通义千问大模型没有完善的go语言兼容openapi示例,并且官方答复assistant是不兼容openapi sdk的。 实际使用中发现是能够支持的,所以自己写了一个demo test示例,给大家做一个参考。
|
1月前
|
程序员 Go
go语言中结构体(Struct)
go语言中结构体(Struct)
113 71
|
1月前
|
存储 Go 索引
go语言中的数组(Array)
go语言中的数组(Array)
116 67
|
1月前
|
Go 索引
go语言for遍历数组或切片
go语言for遍历数组或切片
116 62