1. 树的子结构

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

  1.  3<br />    / \<br />   4   5<br />  / \<br /> 1   2<br />给定的树 B：

4
/
1
返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。

  1. 示例 1：
  3. 输入：A = [1,2,3], B = [3,1]
  4. 输出：false
  5. 示例 2：
  7. 输入：A = [3,4,5,1,2], B = [4,1]
  8. 输出：true

思路：

  • 首先需要找到A节点的某个子节点C的值对应上B节点的值
  • 然后进行探索，C和B是否相同结构，或者C包含B这个结构。—-2

  • 第一步探索结束的条件是：遍历时匹配的节点不为空

  • 找到对应节点后，进行递归探索，也就是上述的第二步，保证当前节点值对应，然后分别判断对左节点和右节点进行递归判断。

  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.         return (A!=null&&B!=null)&&(recur(A,B)||isSubStructure(A.left,B)||isSubStructure(A.right,B));
  13.     }
  15.     private boolean recur(TreeNode A,TreeNode B){
  16.         if(B==null) return true;
  17.         if(A==null || A.val!=B.val) return false;
  18.         return recur(A.left,B.left)&&recur(A.right,B.right);
  19.     }
  20. }