二叉树结构

  1. class TreeNode {
  2.     int val = 0;
  3.     TreeNode left = null;
  4.     TreeNode right = null;
  6.     public TreeNode(int val) {
  7.         this.val = val;
  8.     }
  9. }

题目描述

  • 输入两颗二叉树A，B，判断B是不是A的子结构

解析

  • 二叉树遍历算法的应用
  • 原二叉树是否具有某棵子树，只需要判断每个结点是否都在二叉树中出现即可
  • 第一步在树A中找到和B的根结点的值一样的结点R
  • 第二步再判断树A中以R为根结点的子树是不是包含和树B一样的结构

递归实现

  1. //判断根结点为root1的树是否包含root2结构
  2. public boolean hasSubtree(TreeNode root1,TreeNode root2) {
  3.     //初始化标记变量为false
  4.     boolean hasSubtreeFlag = false;
  6.     //先判断根结点，若不包含判断左孩子，其次是右孩子
  7.     if(root1 != null && root2 != null){
  8.         if(root1.val == root2.val){
  9.             hasSubtreeFlag = nodesValEqual(root1,root2);
  10.         }
  11.         if(!hasSubtreeFlag){
  12.             hasSubtreeFlag = hasSubtree(root1.left,root2);
  13.         }
  14.         if(!hasSubtreeFlag){
  15.             hasSubtreeFlag = hasSubtree(root1.right,root2);
  16.         }
  17.     }
  19.     return hasSubtreeFlag;
  20. }
  22. //判断以root1为根的树上各结点值是否与root2相等
  23. public  boolean nodesValEqual(TreeNode root1, TreeNode root2) {
  25.     if(root2 == null){
  26.         return true;
  27.     }
  28.     if(root1 == null){
  29.         return false;
  30.     }
  31.     if(root1.val != root2.val){
  32.         return false;
  33.     }
  35.     return nodesValEqual(root1.left,root2.left) && nodesValEqual(root1.right,root2.right);
  36. }
  39. <p></p>