首页 > itarticle > 剑指offer_【17】树的子结构

剑指offer_【17】树的子结构

admin 11月 14, 2020 0

1.题目描述

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

2.解题思路

大体思路是首先判断B的根节点和A的根节点是否相同（这里的相同是指节点的值相同并且左右子节点相同），如果相同比较他们的左右子节点，这一步骤是相同的，可以用递归完成，直到B遍历到每个尾节点，如果这一过程比较的所有节点是相同的，则证明B是A的子结构。如果B的根节点和A的根节点不同，则A向他的左右子节点滑动，然后继续跟B的子节点比较，步骤同上。
(1) 如果root1.val==root2.val,那个就以这个为起点判断是否A包含B 

(2) 如果没找到，就以root1.left作为起点继续判断A是否包含B

(3) 如果没找到，再以root1.right作为起点判断A是否包含B

3.代码

public class  {

  public boolean HasSubtree(TreeNode root1, TreeNode root2) {

          boolean result = false;
          
          if (root2 != null && root1 != null) {
              //如果找到了对应Tree2的根节点的点
              if(root1.val == root2.val){
                  //以这个根节点为为起点判断是否包含Tree2
                  result = doesTree1HaveTree(root1,root2);

              }
          //如果找不到，那么就再去root的左儿子当作起点，去判断时候包含Tree2

              if (!result) {
                  result = HasSubtree(root1.left,root2);
              }
        //如果还找不到，那么就再去root的右儿子当作起点，去判断时候包含Tree2

              if (!result) {
                  result = HasSubtree(root1.right,root2);
              }
          }
          //返回结果
          return result;
      }
public boolean doesTree1HaveTree(TreeNode node1, TreeNode node2)  
{        //如果Tree2已经遍历完了都能对应的上，返回true

          if (node2 == null) {
              return true;
          }
          //如果Tree2还没有遍历完，Tree1却遍历完了。返回false
          if (node1 == null) {
              return false;
          }
          //如果其中有一个点没有对应上，返回false
          if (node1.val != node2.val) {
              return false;
          }
          //如果根节点对应的上，那么就分别去子节点里面匹配
          return doesTree1HaveTree(node1.left,node2.left) &&  
                 doesTree1HaveTree(node1.right,node2.right);

      }
  }