go语言算法题解二叉树的拷贝、镜像和对称
Hann Yang 人气:0拷贝副本
复制一个二叉树副本,广度优先遍历同时设置两个队列,一个遍历一个复制创建。
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 }
镜像二叉树
生成一棵二叉树的镜像:
递归法
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多个与二叉树相关的题目,对照看看还有多少没刷过?
加载全部内容