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

软件发布|下载排行|最新软件

当前位置：首页 → IT学院 → IT技术 →

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

Hann Yang   2023-02-03 我要评论

拷贝副本

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

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

相关文章

猜您喜欢

今日热门

Copyright 2022 版权所有 软件发布 访问手机版

声明：所有软件和文章来自软件开发商或者作者 如有异议 请与本站联系 联系我们