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


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




目录
相关文章
|
9月前
|
消息中间件 缓存 NoSQL
Redis各类数据结构详细介绍及其在Go语言Gin框架下实践应用
这只是利用Go语言和Gin框架与Redis交互最基础部分展示;根据具体业务需求可能需要更复杂查询、事务处理或订阅发布功能实现更多高级特性应用场景。
519 86
|
8月前
|
存储 安全 Java
【Golang】(4)Go里面的指针如何?函数与方法怎么不一样?带你了解Go不同于其他高级语言的语法
结构体可以存储一组不同类型的数据,是一种符合类型。Go抛弃了类与继承,同时也抛弃了构造方法,刻意弱化了面向对象的功能,Go并非是一个传统OOP的语言,但是Go依旧有着OOP的影子,通过结构体和方法也可以模拟出一个类。
411 2
|
10月前
|
Cloud Native 安全 Java
Go:为云原生而生的高效语言
Go:为云原生而生的高效语言
625 1
|
11月前
|
Java Shell Maven
【Azure Container App】构建Java应用镜像时候遇无法编译错误:ERROR [build 10/10] RUN ./mvnw.cmd dependency:go-offline -B -Dproduction package
在部署Java应用到Azure Container App时,构建镜像过程中出现错误:“./mvnw.cmd: No such file or directory”。尽管项目根目录包含mvnw和mvnw.cmd文件,但依然报错。问题出现在Dockerfile构建阶段执行`./mvnw dependency:go-offline`命令时,系统提示找不到可执行文件。经过排查,确认是mvnw文件内容异常所致。最终通过重新生成mvnw文件解决该问题,镜像成功构建。
639 1
|
10月前
|
Cloud Native Go API
Go:为云原生而生的高效语言
Go:为云原生而生的高效语言
628 0
|
10月前
|
Cloud Native Java Go
Go:为云原生而生的高效语言
Go:为云原生而生的高效语言
449 0
|
10月前
|
Cloud Native Java 中间件
Go:为云原生而生的高效语言
Go:为云原生而生的高效语言
492 0
|
10月前
|
Cloud Native Java Go
Go:为云原生而生的高效语言
Go:为云原生而生的高效语言
649 0
|
JSON 编解码 API
Go语言网络编程:使用 net/http 构建 RESTful API
本章介绍如何使用 Go 语言的 `net/http` 标准库构建 RESTful API。内容涵盖 RESTful API 的基本概念及规范,包括 GET、POST、PUT 和 DELETE 方法的实现。通过定义用户数据结构和模拟数据库,逐步实现获取用户列表、创建用户、更新用户、删除用户的 HTTP 路由处理函数。同时提供辅助函数用于路径参数解析,并展示如何设置路由器启动服务。最后通过 curl 或 Postman 测试接口功能。章节总结了路由分发、JSON 编解码、方法区分、并发安全管理和路径参数解析等关键点,为更复杂需求推荐第三方框架如 Gin、Echo 和 Chi。
|
10月前
|
数据采集 Go API
Go语言实战案例:多协程并发下载网页内容
本文是《Go语言100个实战案例 · 网络与并发篇》第6篇,讲解如何使用 Goroutine 和 Channel 实现多协程并发抓取网页内容,提升网络请求效率。通过实战掌握高并发编程技巧,构建爬虫、内容聚合器等工具,涵盖 WaitGroup、超时控制、错误处理等核心知识点。