链接

1、题目叙述

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构， 即 A中有出现和B相同的结构和节点值。

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

  1. 输入：A = [1,2,3], B = [3,1]
  2. 输出：false

示例 2：

  1. 输入：A = [3,4,5,1,2], B = [4,1]
  2. 输出：true

限制：
0 <= 节点个数 <= 10000

2、解答

image.png
image.png

image.png

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. class Solution {
  11.     public boolean isSubStructure(TreeNode A, TreeNode B) {
  12.         if(A == null || B == null){
  13.             return false;
  14.         }
  15.         return helper(A,B) || isSubStructure(A.left,B) || isSubStructure(A.right,B);
  16.     }
  18.     public boolean helper(TreeNode A, TreeNode B){
  19.         if(B == null){
  20.             return true;
  21.         }
  22.         //B != null 且 A == null ==> 结构不同
  23.         if(A == null){
  24.             return false;
  25.         }
  26.         return A.val == B.val && helper(A.left, B.left) && helper(A.right, B.right);
  27.     }
  28. }