[Day24]-[二叉树] 相同数

2022 年 4 月 24 日
本文字数：1021 字
阅读完需：约 3 分钟

100. 相同的树

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例 1：

输入：p = [1,2,3], q = [1,2,3]输出：true

复制代码

示例 2：

输入：p = [1,2], q = [1,null,2]输出：false

复制代码

示例 3：

输入：p = [1,2,1], q = [1,1,2]输出：false

复制代码

题解:

深度搜索 DFS

func TestIsSameTree(t *testing.T) {	p := &TreeNode{		Val: 1,		Left: &TreeNode{			Val: 2,		},		Right: &TreeNode{			Val: 3,		},	}	q := &TreeNode{		Val: 1,		Left: &TreeNode{			Val: 2,		},		Right: &TreeNode{			Val: 3,		},	}	var isSameTree func(p *TreeNode, q *TreeNode) bool	isSameTree = func(p, q *TreeNode) bool {		if p == nil && q == nil {			return true		}		if p == nil || q == nil {			return false		}		if q.Val != p.Val {			return false		}
		// 遍历左侧p.Left = 2,q.Left =2		// p.Left=nil,q.Left=nil		// p.Right=nil,q.Right=nil		// p.Right = 3, q.Right=3 // 开始回溯到上个节点		// p.Left = nil,q.Left=nil		// p.Right=nil,q.Right=nil		return isSameTree(p.Left, q.Left) && isSameTree(q.Right, p.Right)	}	t.Log(isSameTree(p, q))}

复制代码

广度搜索 BFS

func TestIsSameTree2(t *testing.T) {	p := &TreeNode{		Val: 1,		Left: &TreeNode{			Val: 2,		},		Right: &TreeNode{			Val: 3,		},	}	q := &TreeNode{		Val: 1,		Left: &TreeNode{			Val: 2,		},		Right: &TreeNode{			Val: 3,		},	}	var isSameTree func(p *TreeNode, q *TreeNode) bool	isSameTree = func(p, q *TreeNode) bool {		if p == nil && q == nil {			return true		}		if p == nil || q == nil {			return false		}		queue := []*TreeNode{}		queue = append(queue, p, q) // 先把p,q root放进去		for len(queue) > 0 {			node1, node2 := queue[0], queue[1] // 每次取两个			queue = queue[2:]                  // 裁剪			if node1 == nil && node2 == nil {  // 都为空 continue				continue			}			if node1 == nil || node2 == nil || node1.Val != node2.Val { // 不相同				return false			}
			queue = append(queue, node1.Left, node2.Left, node1.Right, node2.Right) // 将左右节点放到queue中		}		return true	}	t.Log(isSameTree(p, q))}

复制代码

发布于: 刚刚阅读数: 2

方勇(gopher)

关注

Dead or Alive. 生存战斗是知识的源泉！ 2018.11.08 加入

我是一名SRE哨兵，目前是好大夫基础架构部高级工程师。专注于 SRE，微服务、中间件的稳定性和可用性建设，整体负责好大夫服务治理云平台的设计和搭建！

发布

暂无评论

创作场景

[Day24]-[二叉树] 相同数

100. 相同的树

方勇(gopher)

评论