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


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




目录
相关文章
|
2天前
|
JavaScript Java Go
探索Go语言在微服务架构中的优势
在微服务架构的浪潮中,Go语言以其简洁、高效和并发处理能力脱颖而出。本文将深入探讨Go语言在构建微服务时的性能优势,包括其在内存管理、网络编程、并发模型以及工具链支持方面的特点。通过对比其他流行语言,我们将揭示Go语言如何成为微服务架构中的一股清流。
|
2天前
|
SQL 关系型数据库 MySQL
go语言中安装数据库驱动
【11月更文挑战第1天】
15 5
|
2天前
|
编译器 Go 开发者
go语言中导入相关包
【11月更文挑战第1天】
10 3
|
2天前
|
关系型数据库 MySQL 数据库连接
go语言中打开数据库连接
【11月更文挑战第1天】
12 2
|
3天前
|
安全 测试技术 Go
Go语言中的并发编程模型解析####
在当今的软件开发领域,高效的并发处理能力是提升系统性能的关键。本文深入探讨了Go语言独特的并发编程模型——goroutines和channels,通过实例解析其工作原理、优势及最佳实践,旨在为开发者提供实用的Go语言并发编程指南。 ####
|
6月前
|
开发框架 安全 中间件
Go语言开发小技巧&易错点100例(十二)
Go语言开发小技巧&易错点100例(十二)
74 1
|
8天前
|
Go 数据安全/隐私保护 开发者
Go语言开发
【10月更文挑战第26天】Go语言开发
24 3
|
10天前
|
Java 程序员 Go
Go语言的开发
【10月更文挑战第25天】Go语言的开发
20 3
|
3月前
|
JSON 中间件 Go
go语言后端开发学习(四) —— 在go项目中使用Zap日志库
本文详细介绍了如何在Go项目中集成并配置Zap日志库。首先通过`go get -u go.uber.org/zap`命令安装Zap,接着展示了`Logger`与`Sugared Logger`两种日志记录器的基本用法。随后深入探讨了Zap的高级配置,包括如何将日志输出至文件、调整时间格式、记录调用者信息以及日志分割等。最后,文章演示了如何在gin框架中集成Zap,通过自定义中间件实现了日志记录和异常恢复功能。通过这些步骤,读者可以掌握Zap在实际项目中的应用与定制方法
125 1
go语言后端开发学习(四) —— 在go项目中使用Zap日志库
|
3月前
|
算法 NoSQL 中间件
go语言后端开发学习(六) ——基于雪花算法生成用户ID
本文介绍了分布式ID生成中的Snowflake(雪花)算法。为解决用户ID安全性与唯一性问题,Snowflake算法生成的ID具备全局唯一性、递增性、高可用性和高性能性等特点。64位ID由符号位(固定为0)、41位时间戳、10位标识位(含数据中心与机器ID)及12位序列号组成。面对ID重复风险,可通过预分配、动态或统一分配标识位解决。Go语言实现示例展示了如何使用第三方包`sonyflake`生成ID,确保不同节点产生的ID始终唯一。
go语言后端开发学习(六) ——基于雪花算法生成用户ID

热门文章

最新文章