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

---