剑指offer——第8期

2022-09-22 79

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 剑指offer——第8期

里面有非常多的题库跟面经知识真的非常良心了！！

JZ26 树的子结构

题目描述

解题思路

1、先定义一个方法，传入两棵根节点值相同的树，判断root1是否和root2结构一样

2、再写一个方法来遍历大树，找到一个和小树根节点值相等的节点，以该节点和小树根节点的值为参数调用上面的方法即可

代码详解

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(root1==null || root2==null) return false;//题目要求，空树不是任何树的子结构
        return IsChildTree(root1,root2)||HasSubtree(root1.left,root2)||
            HasSubtree(root1.right,root2);
      }  
       //当两颗树根节点相同时 判断root1 是否和root2结构一样
       boolean IsChildTree(TreeNode root1,TreeNode root2){
        if(root2==null) return true;
        if(root1==null) return false;
        if(root1.val!=root2.val && root2.val!=root1.val) return false;
    return IsChildTree(root1.left,root2.left)&&IsChildTree(root1.right,root2.right);
    }
}

JZ25 合并两个排序的链表

题目描述

解题思路

新建一个虚拟头结点用来合并链表,如果list1的结点值小于list2的结点值 则将lsit1指向的结点值接到head的next指针后面然后指向下一个节点否则让 list2指向下一个节点把未结束的链表连接到合并后的链表尾部最后将剩下的部分连接到root后面

代码详解

import java.util.*;
/*
public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        ListNode head=new ListNode(-1);//新建一个虚拟头结点 用来合并链表
        head.next=null;
        ListNode root=head;
        while(list1!=null&&list2!=null){ //如果list1的结点值小于list2的结点值 则将
            //lsit1指向的结点值接到head的next指针后面 然后指向下一个节点
            if(list1.val<list2.val){ //否则让 list2指向下一个节点
                head.next=list1;
                head=list1;
                list1=list1.next;
            }else{
                head.next=list2;
                head=list2;
                list2=list2.next;
            }
        }
        //把未结束的链表连接到合并后的链表尾部
        if(list1!=null) head.next=list1; //最后将剩下的部分连接到root后面
        if(list2!=null) head.next=list2;
        return root.next;
    }
}