剑指offer—二叉树的子树 解答

剑指offer—二叉树的子树

题目描述

输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构)

示例 2:
给定的树 s:

     3
    / \
   4   5
  / \
 1   2
    /
   0
给定的树 t:

   4
  / \
 1   2
返回 true

思路

s树为需要查找的树,t树为判断是否存在的子树

分为两步骤:

  1. 找到和t树根节点元素相等的s树中的节点
  2. 判断该节点下面的子树是否符合t树的结构和值

首先我们可以用递归找到元素值相等的节点,找到后执行判断是否为子树,如果为false,接着往该节点左边找,还为false往右边找,最后遍历完s树返回结果

判断是否为子树:

  • 先判断t节点是否为空,为空说明s中包含该t子树,返回true
  • 再判断s是否为空,这是在t不为空的基础上,则说明不包含t子树,返回false
  • 如果s、t都不为空,判断两值是否相等,不相等返回false
  • 如果相等再使用递归判断它们的左子数和右子树是否为子树

代码

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public boolean HasSubtree(TreeNode s,TreeNode t) {
        boolean result = false;
        if(s!=null&&t!=null){//s和t都不为空
            if(s.val==t.val){//找到了相等元素
                //判断s下面的结构有没有t
                result = isEquals(s,t);
            }
            if(!result){//如果没有找到或者找到的不满足子树要求,再找左节点
                result = HasSubtree(s.left,t);
            }
            if(!result){//如果没有找到或者找到的不满足子树要求,再找右节点
                result = HasSubtree(s.right,t);
            }
        }
        return result;
    }
    //判断是否为子树
    public boolean isEquals(TreeNode s,TreeNode t){
        if(t==null){//为null说明包含
            return true;
        }
        if(s==null){//t不为null s为null说明不包含
            return false;
        }
        if(s.val!=t.val){//不相等说明不包含
            return false;
        }
        return isEquals(s.left,t.left)&&isEquals(s.right,t.right);//相等则判断左节点和有节点是否满足
    }
}

扩展—LeetCode572

题目描述

给定两个非空二叉树 s 和 t,检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。

示例 2:
给定的树 s:

     3
    / \
   4   5
  / \
 1   2
    /
   0
给定的树 t:

   4
  / \
 1   2
返回 false。

当s子树和t不完全相同时(有多余元素),则返回false

思路

  • 只需要更改判断子树条件即可
  1. 如果s或者t其中只有一个为null,说明子树不完全相同,返回false
  2. 如果同时为null说明完全相同,返回true
  3. 如果值不相同,返回false

代码

class Solution {
    public boolean isSubtree(TreeNode s, TreeNode t) {
        boolean result = false;
        if(s!=null&&t!=null){
            if(s.val==t.val){
                //判断s下面的结构有没有t
                result = isEquals(s,t);
            }
            if(!result){
                result = isSubtree(s.left,t);
            }
            if(!result){
                result = isSubtree(s.right,t);
            }
        }
        return result;
    }

    public boolean isEquals(TreeNode s,TreeNode t){
        if((t==null&&s!=null)||(t!=null&&s==null)){
            return false;
        }
        if(s==null&&t==null){
            return true;
        }
        if(s.val!=t.val){
            return false;
        }else{
            return isEquals(s.left,t.left)&&isEquals(s.right,t.right);
        }
    }
}