侧边栏壁纸
博主头像
Johnny博主等级

学无先后,达者为师

  • 累计撰写 11 篇文章
  • 累计创建 4 个标签
  • 累计收到 1 条评论

目 录CONTENT

文章目录

二叉树子树

Johnny
2022-08-13 / 0 评论 / 0 点赞 / 46 阅读 / 484 字

二叉树子树

LeetCode 100. 相同的树

func isSameTree(p *TreeNode, q *TreeNode) bool {
    if p == nil && q == nil {
		return true
	} else if p != nil && q != nil {
		if p.Val != q.Val {
			return false
		}
		return isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
	} else {
		return false
	}
}

本题就很简单的逻辑,把左右子树的节点全部比一边,递归就可以解出。主要通过这题看下面的这一道题目

LeetCode 572.另一棵树的子树

func isSubtree(s *TreeNode, t *TreeNode) bool {
    if s==nil{
        return false
    }
    return isSameTree(s,t)||isSubtree(s.Left,t)||isSubtree(s.Right,t)
}

func isSameTree(p *TreeNode, q *TreeNode) bool {
    if p == nil && q == nil {
		return true
	} else if p != nil && q != nil {
		if p.Val != q.Val {
			return false
		}
		return isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
	} else {
		return false
	}
}

下面的代码是不是似曾相识。

这个思路也是看别人的题解看到的,因为我是一个算法菜鸡,这几天多看点别人的思路,积累一下。思路如下(来源与Leetcode用户fuxuemingzhu):

要判断一个树 t 是不是树 s 的子树,那么可以判断 t 是否和树 s 的任意子树相等。那么就转化成 100. Same Tree。
即,这个题的做法就是在 s 的每个子节点上,判断该子节点是否和 t 相等。

判断两个树是否相等的三个条件是与的关系,即:

  1. 当前两个树的根节点值相等;

  2. 并且,s 的左子树和 t 的左子树相等;

  3. 并且,s 的右子树和 t 的右子树相等。

    而判断 t 是否为 s 的子树的三个条件是或的关系,即:

  4. 当前两棵树相等;

  5. 或者,t 是 s 的左子树;

  6. 或者,t 是 s 的右子树。

所以在isSubtree的递归返回就是一系列的或和左右子树的递归比较

0

评论区