[每日一道算法（二十七）][二叉树] 树的子结构（剑指offer题）

亦凉 2023-07-05 10:13 4阅读 0赞

前言：  
树的题真是不好想，慢慢来吧。

### 题目描述 ###

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

### 题目解析 ###

这道题我们可以分成两步：第一步，在树A中找到和树B的根节点的值一样的节点R，第二步：判断树A中以R为根节点的子树是不是包含和树B一样的结构。  
我们通过递归的方式，左右分别查找，最终如果不匹配则返回false。

### 代码样例 ###

package com.asong.leetcode.HasSubtree;
    
    /** * 树的子结构： 题目描述： 输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构） */
    
    public class Solution1 { 
        public boolean HasSubtree(TreeNode root1,TreeNode root2) { 
            boolean result = false;
            //两个都不为空的时候才进行比较
            if(root1!=null && root2!=null)
            { 
                if(root1.val==root2.val)
                { 
                    result =  DoesTreeHaveTree(root1,root2);
                }
                if(!result)
                { 
                    result = DoesTreeHaveTree(root1.left,root2);
                }
                if(!result)
                { 
                    result = DoesTreeHaveTree(root1.right,root2);
                }
            }
            return result;
        }
        public static boolean DoesTreeHaveTree(TreeNode root1,TreeNode root2)
        { 
            //如果root2为空了，则代表都匹配上了，则返回true
            if(root2 == null)
            { 
                return true;
            }
            //如果root1为空了，则为匹配上
            if(root1 == null)
            { 
                return false;
            }
            //如果没找到相等的值，则也未匹配上
            if(root1.val != root2.val)
            { 
                return false;
            }
            return DoesTreeHaveTree(root1.left,root2.left) && DoesTreeHaveTree(root1.right,root2.right);
        }
    }