剑指offer：树的子结构（Java）

taoszu 发布于2019-08-16 18:40 / 2522人阅读

摘要：问题描述输入两棵二叉树，，判断是不是的子结构。调用方法判断是不是的子结构当前两个根节点的值不相等就判断的左子节点是否和节点相等的左子树的节点都和不等的情况下判断的右子树节点和是不是相等。

1.问题描述

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

2.思路

首先根据题目，只有两个树都不为null时才需要进行判断，否则直接返回false。
然后就是遍历大树，找小树的头节点，如果遍历完都没找到，就是false
如果找到小树的头节点，就依次比较后面对应的左右子节点，如果有一个不相等就是false，
一一对应到最后时，肯定是小树的节点为null，大树不一定为null，所以先用小树判断。
如果大树为null了，小树还不是，说明小树不是大树的子结构，返回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 root1,TreeNode root2) {
        boolean result = false;    //用来记录判断结果
        if(root1 != null && root2 != null){    //只有两个根节点都不为null时才进行判断，否则直接返回false。
                result = doesTree1HaveTree2(root1,root2);    //调用doesTree1HaveTree2方法判断Tree2是不是Tree1的子结构
            if(!result){    //当前两个根节点的值不相等就判断root1的左子节点是否和root2节点相等
                result = doesTree1HaveTree2(root1.left,root2);
            }
            if(!result){    //root1的左子树的节点都和root2不等的情况下判断root1的右子树节点和root2是不是相等。
                result = doesTree1HaveTree2(root1.right, root2);
            }
        }
        return result;    //root1都遍历完成后返回结果。
    }
    
    public boolean doesTree1HaveTree2(TreeNode node1, TreeNode node2){
        if(node2 == null){    //如果node2树先遍历完了都和node1对上，说明node2是node1的子结构返回true
            return true;
        }
        if(node1 == null){    //如果node2不为null而node1为null了说名node2不是node1的子结构，返回false
            return false;
        }
        if(node1.val != node2.val){    //只要判断过程中有一个不想等直接返回false，这里注意只是判断一个子树没有匹配的，在HasSubTree中还会判断右子树中是否存在root2结构，所以不会漏掉。
            return false;
        }
        return doesTree1HaveTree2(node1.left, node2.left) && doesTree1HaveTree2(node1.right, node2.right);
        //当前节点的值相等，判断左右两个子节点的值是不是相等，有一个不等就返回false。
    }
}

注意：

(1)doesTree1HaveTree2方法中判断小树是否为null必须放在前面，不能和判断大树是否为null交换，因为如果换了的话，在大树为null时，小树不确定，小树如果也为null，就应该是true，而这时返回的是false，就是错误的。
(2)如果根节点的左子树中有小树的一部分，而右子树中有整个小树，这种情况不会漏掉，因为在HasSubTree方法中是先判断左子树，在判断右子树，左子树返回false时，会在右子树中重新找小树的根节点，所以不会漏掉。

参考
Boooobby的牛客网答案

GPU云服务器云服务器二叉树的存储结构 java菜单树的实现 java二叉树的构建 java树的使用方法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/75533.html

【剑指offer】5.二叉树的镜像和打印

摘要：题目二叉树的镜像题目描述操作给定的二叉树，将其变换为源二叉树的镜像。代码题目从上往下打印二叉树题目描述从上往下打印出二叉树的每个节点，同层节点从左至右打印。解题思路借助队列先进先出的数据结构让二叉树每层依次进入队列依次打印队列中的值代码二叉树简介基本结构： function TreeNode(x) { this.val = x; this.left = null; ...

villainhr 2019-08-23 14:43 评论0 收藏0
从简历被拒到收割今日头条 offer，我用一年时间破茧成蝶！

摘要：正如我标题所说，简历被拒。看了我简历之后说头条竞争激烈，我背景不够，点到为止。。三准备面试其实从三月份投递简历开始准备面试到四月份收，也不过个月的时间，但这都是建立在我过去一年的积累啊。本文是无精疯同学投稿的面试经历关注微信公众号：进击的java程序员K，即可获取最新BAT面试资料一份在此感谢无精疯同学的分享目录：印象中的头条面试背景准备面试 ...

tracymac7 2019-08-15 17:57 评论0 收藏0
从简历被拒到收割今日头条 offer，我用一年时间破茧成蝶！

摘要：正如我标题所说，简历被拒。看了我简历之后说头条竞争激烈，我背景不够，点到为止。。三准备面试其实从三月份投递简历开始准备面试到四月份收，也不过个月的时间，但这都是建立在我过去一年的积累啊。本文是无精疯同学投稿的面试经历关注微信公众号：进击的java程序员K，即可获取最新BAT面试资料一份在此感谢无精疯同学的分享目录：印象中的头条面试背景准备面试头条一面（Java+项目）头条...

wdzgege 2019-08-19 11:43 评论0 收藏0
PHPer面试必看：分门别类带你撸《剑指Offer》之二叉树

摘要：例如输入前序遍历序列和中序遍历序列，则重建二叉树并返回。操作给定的二叉树，将其变换为源二叉树的镜像。剑指中还有一道类似的变种题目，就是下面的这道，之字形遍历二叉树。最后下面的两道题目分别运用了二叉树先序中序遍历算法。开篇以下内容可能偏应试但很好理解，所以大家一定要坚持看下去，因为我们变强的过程注定孤独的，坚持下来就会看到明天的太阳。回顾 showImg(https://user-...

li21 2019-07-01 10:26 评论0 收藏0
Java实现基本数据结构2（树）

摘要：实现基本数据结构栈，队列，链表这篇笔记侧重点二叉树的三种遍历前中后迭代非迭代代码重建二叉树的代码与分析和关于二叉树的题简单理解二叉查找树红黑树，的性质，实际用途。同时，以对应的节点为边界，就会把中序遍历的结果分为左子树和右子树。虽是读书笔记，但是如转载请注明出处 http://segmentfault.com/blog/exploring/ .. 拒绝伸手复制党以下是算法导论第十...

opengps 2019-08-14 12:06 评论0 收藏0