categories: [Blog,Algorithm]

572. 另一个树的子树

难度简单451
给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。
示例 1:
给定的树 s:
3
/ \
4 5
/ \
1 2

给定的树 t：
4
/ \
1 2

返回 true，因为 t 与 s 的一个子树拥有相同的结构和节点值。
示例 2:
给定的树 s：
3
/ \
4 5
/ \
1 2
/
0

给定的树 t：
4
/ \
1 2

返回 false。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  17.     public boolean isSubtree(TreeNode s, TreeNode t) {
  18.         return dfs(s, t);
  19.     }
  21.     public boolean dfs(TreeNode s, TreeNode t) {
  22.         if (s == null) {//题干:检验 s 中是否包含和 t 具有相同结构和节点值的子树。
  23.             return false;
  24.         }
  25.         return check(s, t) || dfs(s.left, t) || dfs(s.right, t);
  26.     }
  28.     public boolean check(TreeNode s, TreeNode t) {
  29.         if (s == null && t == null) {
  30.             return true;
  31.         }
  32.         if (s == null || t == null || s.val != t.val) {
  33.             return false;
  34.         }
  35.         return check(s.left, t.left) && check(s.right, t.right);
  36.     }
  38. // 作者：LeetCode-Solution
  39. // 链接：https://leetcode-cn.com/problems/subtree-of-another-tree/solution/ling-yi-ge-shu-de-zi-shu-by-leetcode-solution/
  40. }