当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.572.Subtree of Another Tree 判断是否二叉树的子树

LeetCode.572.Subtree of Another Tree 判断是否二叉树的子树

题目描述

572 Subtree of Another Tree
https://leetcode-cn.com/problems/subtree-of-another-tree/

Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node’s descendants. The tree s could also be considered as a subtree of itself.

Example 1:
Given tree s:

     3
    / \
   4   5
  / \
 1   2

Given tree t:

   4
  / \
 1   2

Return true, because t has the same structure and node values with a subtree of s.

Example 2:
Given tree s:

     3
    / \
   4   5
  / \
 1   2
    /
   0

Given tree t:

   4
  / \
 1   2

Return false.


相似题目

LeetCode.100.Same Tree 相同的树
LeetCode.572.Subtree of Another Tree 判断是否二叉树的子树


解题过程

判断一个树是否另一个树的子树, 递归求解。
递归遍历s树O(m),对每个子树都和t比较是否相等 O(n),总的时间复杂度为 O(mn)
空间复杂度 O(n)

递归判断

private static class SolutionV2020 {
    // 判断t是否s的子树
    public boolean isSubtree(TreeNode s, TreeNode t) {
        if (null == s && null == t) {
            return true;
        }
        if (null == s || null == t) {
            return false;
        }
        return identity(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t);
    }

    // 判断两棵树是否相同
    private boolean identity(TreeNode root1, TreeNode root2) {
        if (null == root1 && null == root2) {
            return true;
        }
        if (null == root1 || null == root2) {
            return false;
        }
        boolean res = root1.val == root2.val && identity(root1.left, root2.left) && identity(root1.right, root2.right);
        return res;
    }
}

转为先序序列后判断是否子串

注意直接转为先序序列后判断 t 是否 s 的子串是不对的,因为当左右某一子树为空时就丢了有序性
比如

   1     1
  /       \
2          2

先序序列都是 1 2,无法区分,解决方法是给空子树补上值,左空子树用 “LeftNull” 代替,右空子树用 “RightNull” 代替。


GitHub代码

algorithms/leetcode/leetcode/_572_SubtreeOfAnotherTree.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_572_SubtreeOfAnotherTree.java


上一篇 LeetCode.530.Minimum Absolute Difference in BST 非负BST的最小绝对差

下一篇 LeetCode.606.Construct String from Binary Tree 二叉树转括号字符串

阅读
评论
435
阅读预计2分钟
创建日期 2020-01-30
修改日期 2020-05-07
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论