每日一题
相同的树
跳转链接
![image-20211230101007139](https://img.helloteemo.com.cn/2021/12/30/1640830209.png)
题目
这道题就是一个很简单的前序遍历,我们先来看下函数签名
| func isSameTree(p *TreeNode, q *TreeNode) bool { }
|
其中形参是两个树,我们需要返回两个树是否相等。树的题目我们都是可以使用递归来解决问题的,
确定递归框架
树的递归有三种方式: 前序遍历、中顺遍历、后序遍历
。他们的伪代码可以简单的概括一下
1 2 3 4 5 6 7 8 9 10
| func traverse(p *TreeNode) { if p == nil { return } traverse(root.left) traverse(root.right) }
|
那么这道题应该使用什么遍历方式呢,我们由题目可以知道: 树的结构相同、并且节点具有相同的值。如果节点的值不相等的话可以直接判定他们不是一颗相等的树,而这种预先使用节点的方式正是前序遍历。
确定函数退出方式
根据题目可以知道:一颗相同的树需要树的结构相同、并且节点具有相同的值,那么一棵树只要节点不相等、节点的值不同就可以判定为false
,由此可得函数的退出方式代码为
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| func isSameTree(p *TreeNode, q *TreeNode) bool { if p == nil && q == nil{ return true } if q==nil || p == nil{ return false } if p.Val != q.Val{ return false } }
|
最后的代码
1 2 3 4 5 6 7 8 9 10
| func isSameTree(p *TreeNode, q *TreeNode) bool { if p == nil && q == nil{ return true } if q==nil || p == nil{ return false } return p.Val == q.Val && isSameTree(p.Left,q.Left) && isSameTree(p.Right,q.Right) }
|
![image-20211230103553231](https://img.helloteemo.com.cn/2021/12/30/1640831755.png)
写在最后
每日一题走起来啊.因为是第一篇文章,所以解题过程写的比较详细。