实习+秋招刷题023-024（牛客刷题）剑指offer

023树的子结构
题目描述
输入两棵二叉树A，B，判断B是不是A的子结构。（我们约定空树不是任意一个树的子结构）
假如给定A为{8,8,7,9,2,#,#,#,#,4,7}，B为{8,9,2}，2个树的结构如下，可以看出B是A的子结构

关键解题思路
dfs（深度优先遍历）、递归
1、递归判断A的子树里有没有子结构
（1）结束边界条件：两者中任意一个为空树，返回false
（2）本级任务：递归确认是否是子结构，dfs递归判断左右节点有没有子结构。
2、确认是否是子结构
（1）结束条件：Aroot为空且Broot不为空，Broot为空，两个头结点值不同
（2）本级任务：判断两个树各自左右节点是否为子结构。
Solution

import java.util.*;
/** 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) {
   
        if ( root2 == null || root1 == null) {
   
            return false;        }
        //判断是否子结构
        if(doesTree1HasTree2(root1, root2)) return true;
        //dfs判断A的左右节点有无子结构
        return HasSubtree(root1.left, root2) ||
               HasSubtree(root1.right, root2);
    }
    public boolean doesTree1HasTree2(TreeNode tree1, TreeNode tree2) {
   
        if ( tree2 == null ) {
   
            return true;
        }
        if ( tree1 == null ) {
   
            return false;
        }
        if ( tree1.val != tree2.val ) {
   
            return false;
        }
        return doesTree1HasTree2(tree1.left, tree2.left) &&
               doesTree1HasTree2(tree1.right, tree2.right);
    }
}

024 包含min函数的栈
题目描述

关键解题思路

Solution