[名企面试知识点][Java]判断树B是不是树A的子结构
发布于 2017-03-09 14:35 1766 次浏览 0 赞 来自 笔试面试  

题目描述

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

输入描述

两颗二叉树A,B

输出描述

boolean值

题目分析

树节点声明:

public class TreeNode {
   int val = 0;
   TreeNode left = null;
   TreeNode right = null;
   public TreeNode(int val) {
       this.val = val;
   }
}

解法  运行时间:30ms  占用内存:629k

public class Solution {
   //判断root1为根节点的树 是否包含 root2为根的树
   public boolean HasSubtree(TreeNode root1,TreeNode root2) {

     //如果其中有一个节点为空就返回false
       if (root1 == null || root2 == null) return false;

   // 如果root2为根节点的树 是 root1为根的树的子树,返回true;否则依次遍历左右子节点再做判断
   return isSubtree(root1,root2)||
         HasSubtree(root1.left,root2)||
          HasSubtree(root1.right,root2);

   } 
   //判断root2为根节点的树 是否为 root1为根的树的子树
   public boolean  isSubtree(TreeNode root1, TreeNode root2) {
       if (root2 == null) return true;
       if (root1 == null) return false;

       if (root2.val == root1.val) {
       //如果根节点相同分别遍历左右子树,看是否相同
        return isSubtree(root1.left, root2.left)&&                            isSubtree(root1.right, root2.right);
       }else {
           return false;
       }
   }
}

首先需要递归root1树,找到与root2根一样的节点;

找到相同的根节点后,要判断是否子树(及左右节点都相等),都相等返回true,否则返回false;


添加回复
回到顶部