题目描述

输入两棵二叉树A，B，判断 B 是不是 A 的子结构。（ps：我们约定空树不是任意一个树的子结构）

https://www.nowcoder.com/practice/6e196c44c7004d15b1610b9afca8bd88

解题想法

找到相同的根节点，遍历左右子树，相同返回 true

  1. 遍历大树，找到两个相同值的根节点

  2. 对相同的节点子树进行遍历，若有不同的返回 false。

  3. 若 B 为 null，说明子树遍历完成都相同，返回 true。若 A 为 null，说明父树遍历完成还没有找到相同的，返回 false。

要注意的是，对子节点进行遍历时，应该先判断 B 是否为 null，再判断 A 是否为 null。因为 A 节点为 null 时候，B 节点也可能为 null，但 B 是 A 的子结构。

代码实现

  2. /**
  3. public class TreeNode {
  4.     int val = 0;
  5.     TreeNode left = null;
  6.     TreeNode right = null;
  8.     public TreeNode(int val) {
  9.         this.val = val;
  10.     }
  11. }
  12. */
  13. public class Solution {
  14.     public boolean HasSubtree(TreeNode root1,TreeNode root2) {
  15.         // 题目中标明 null 不为任一子结构
  16.         if (root1 == null || root2 == null){
  17.             return false;
  18.         }
  19.         // 当前节点相同，那么继续遍历子节点
  20.         if (root1.val == root2.val){
  21.             if (isOK(root1,root2)){
  22.                 return true;
  23.             }
  24.         }
  25.         // 在父树的子树中找到值相同的节点，然后进行判断
  26.         return HasSubtree(root1.left,root2) || HasSubtree(root1.right,root2);
  27.     }
  29.     // 对两个值相同的节点，进行遍历，判断 root2 是否是子结构
  30.     public boolean isOK(TreeNode root1,TreeNode root2){
  31.         // 必须先判断 root2，当 root2 为 null 时，就不用管 root1 的值
  32.         if (root2 == null){
  33.             return true;
  34.         }
  35.         // 此时 root2 != null 而 root1 == null，那么返回 false
  36.         if (root1 == null){
  37.             return false;
  38.         }
  39.         // 节点值有不一样的
  40.         if (root1.val != root2.val){
  41.             return false;
  42.         }
  43.         // 遍历左右子树，不一样返回 false，直到 root2 == null
  44.         return isOK(root1.left,root2.left) && isOK(root1.right,root2.right);
  45.     }
  47. }