每日一题

相同的树

跳转链接

image-20211230101007139

题目

这道题就是一个很简单的前序遍历，我们先来看下函数签名

func isSameTree(p *TreeNode, q *TreeNode) bool {
	
}

其中形参是两个树，我们需要返回两个树是否相等。树的题目我们都是可以使用递归来解决问题的，

确定递归框架

树的递归有三种方式: 前序遍历、中顺遍历、后序遍历。他们的伪代码可以简单的概括一下

func traverse(p *TreeNode) {
    if p == nil {
        return 
    }
	// 前序遍历
    traverse(root.left)
    // 中序遍历
    traverse(root.right)
    // 后序遍历
}

那么这道题应该使用什么遍历方式呢，我们由题目可以知道: 树的结构相同、并且节点具有相同的值。如果节点的值不相等的话可以直接判定他们不是一颗相等的树，而这种预先使用节点的方式正是前序遍历。

确定函数退出方式

根据题目可以知道：一颗相同的树需要树的结构相同、并且节点具有相同的值，那么一棵树只要节点不相等、节点的值不同就可以判定为false，由此可得函数的退出方式代码为

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
    }
    // isSameTree(p.Left,q.Left)
    // isSameTree(p.Right,q.Right)
    
}

最后的代码

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

写在最后

每日一题走起来啊.因为是第一篇文章，所以解题过程写的比较详细。