11.23二叉树

目录

一.笔试强训习题订正

1.选择题

2.编程题-组队竞赛

3.删除公共字符

解法1 哈希映射思想

解法2 暴力解法

解法3 substring解法+replaceAll()

二.二叉树相关Oj题

1.二叉树的遍历

2.二叉树分层遍历

三.二叉树的最近公共祖先

1.思路一

2.思路2

四.将二叉搜索树转化为有序链表

---

一.笔试强训习题订正

1.选择题

向上取整

2.编程题-组队竞赛

这道题的题眼就是水平值是第二稿水平值 也就是123 是2

并且几组就是水平置相加

这道题的思路就是先读取输入的组成的队伍

然后读取每一个元素.放入数组里

因为参加比赛的一定是3*n个选手,所以一定是数组的长度一定是

3*n

所以也好初始化数组

然后给数组排序

我们的解题思路就是每次从数组的第一个元素和最后两个取两个元素作为一组,这样就能保证每个水平最大值

要注意输入输出

先排序

假设排序后是： 1 2 3 4 5 6 7 8 9

1 和 8 9 为一组

2 和 6 7 为一组

3 和 4 5为一组

每组第二大的数字为 8 6 4

其 size=9 ;  

import java.util.*;
public  class Main{
     public static void main(String[] args){
         Scanner sc=new Scanner(System.in);
         while(sc.hasNextInt()){
             int n=sc.nextInt();
              long sum=0;
             int[] array=new int[3*n];
             for(int i=0;i<3*n;i++){
                 array[i]=sc.nextInt();
             }
         Arrays.sort(array);//数组排序
         for(int i=1;i<=n;i++){
             sum+=array[3*n-i*2];
         }
         System.out.println(sum);
         }
    }
}

这道题 刚开始我害怕可能任务这是一组队列题,其实这里看到分组就要往数组靠.

还有第二行多组输入的时候不需要处理循环,就直接用一个for循环来处理每一个来接收,

还有复习到了一个数组排序公式

Arrays.sort(数组名);

3.删除公共字符

解法1 哈希映射思想

先遍历第二个字符串,因为一个哈希数组初始都为0

就先把遍历到的字符在哈希表找到对应的位置置为1

然后遍历字符串1.每遍历一个不是1的就打印\

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        String str1=sc.nextLine();
        String str2=sc.nextLine();
        char[] hash=new char[256];
        for(int i=0;i
            hash[str2.charAt(i)]++;
        }
        for(int i=0;i
            if(hash[str1.charAt(i)]==0){
                System.out.print(str1.charAt(i));
            }
        }
    }
}

解法2 暴力解法

遍历字符串1,

每遍历一个元素就开始遍历字符串2有没有相同元素,如果有,就不打印.结束循环就打印.

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        String str1=sc.nextLine();
        String str2=sc.nextLine();
       for(int i =0;i
           char ch=str1.charAt(i);
           int a=0;
           for(int j=0;j
               if(ch==str2.charAt(j)){
                   a=1;
                   break;
               }
           }
           if(a==0){
               System.out.print(ch);
           }
       }
    }
}

解法3 substring解法+replaceAll()

这种方法要对string的各种方法熟稔于心

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        String str1=sc.nextLine();
        String str2=sc.nextLine();
           for(int j=0;j
              str1=str1.replaceAll(str2.substring(j,j+1),"");
           }
        System.out.println(str1);
 
      }
}

遍历字符串2.从第一个元素开始,如果有相同的就替换为""也就是没有

二.二叉树相关Oj题

1.二叉树的遍历

import java.util.*;
class TreeNode {
    TreeNode left;
    TreeNode right;
    char  val;
    TreeNode(char val) {
        this.val = val;
    }
}
 
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void inorder(TreeNode root) {
        if (root == null) return;
        inorder(root.left);
        System.out.print(root.val + " ");
        inorder(root.right);
 
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String str = in.nextLine();
            TreeNode root = creat(str);
            inorder(root);
            System.out.println();
        }
    }
 
        public static int i = 0;
        public static TreeNode creat(String ret) {
            TreeNode root =null;
            if (ret.charAt(i) != '#') {
               root=new TreeNode(ret.charAt(i));
                i++;
                root.left = creat(ret);
                root.right = creat(ret);
            } else {
                i++;
            }
            return root;
        }
    }

这里我出现了一些问题

在创建二叉树这一步,我先入为主直接初始化根,先不说没有考虑到第一个节点就是空的,也就是这棵树就是空树.也没有考虑到假如树的分节点是空的,进入递归,直接创建了一个内容是#的树而不是返回空.逻辑出错

最好的方法就是初始化先是null.判断是否为#.是就初始化,并i++.进入left.或者就是null并i+=

往后遍历

2.二叉树分层遍历

这里我们考虑到用队列.先进先出,底层用顺序表也就是数组存放每一层

遍历树.判断是否为空,不是就是放入他的左子树和右子树.并打印他,

如果是空,就不打印

这样从左向右打印

class Solution {
    public List> levelOrder(TreeNode root) {
        List> lists=new ArrayList<>();
         if(root==null) return lists;
        Queue queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            List list=new ArrayList<>();
            int size=queue.size();//求队列长度没有length公式只有大小的
            while(size!=0){
               TreeNode cur=queue.poll();
               list.add(cur.val);
               if(cur.left!=null){
               queue.offer(cur.left);
              } 
              if(cur.right!=null){
               queue.offer(cur.right);
              }
            size--;
            }
            lists.add(list);
        }
        return lists;
    }
}

注意队列的长度公式.只有里面有多少元素 的公式也就是 queue.size()

这道题怎么样分层

就是求每一次循环得到的队列长度,然后循环放入

并且每次放入顺序表里,都会弹出.这样保证上一层的空了

这种情况,遇到最后一组,会显示还有元素,就继续进入循环,但是因为是空的,所以不放元素,但是还是一组表,就会显示多一层

所以还是得分开进行判断放元素

这道题还有很多问法

1.求二叉树的左视图,其实就是链表的每组数组的第一个元素

2.求二叉树的宽度,其实就是数组最长的,

三.二叉树的最近公共祖先

1.思路一

如果给定的树是一颗二叉搜索树

根节点的左子树都比根小

根节点的右子树都比根大

根据中序遍历 : 左子树-根-右子树

我们可以思考

就按根节点来想.如果

1.p是root或者q是root

2.如果p的值和q的值都小于root.那么就说明公共祖先都在root的左树

那就说明公共祖先是在root的左树中

3.如果p的值和q的值都大于root.那么就说明公共祖先都在root的右树

那就说明公共祖先是root的右树

4.如果一个大于根节点另外一个小于根节点,就说明一个在左子树,一个在右子树

那么公共祖先就是root

那么我们可以往后递归,再对root,left和root.right进行判断递归

直到找到满足条件

那么我们再发散一下,如果他只是一颗普通的树呢

那就分别在左子树和右子树找到p或者q,如果能在左子树或者右子树找到那就返回找到的节点

但是如果左子树和右子树都找到了.那就返回根节点

如果都没有就返回null

然后再发散一下

递归根节点,传递的p和q不变

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null) return null;
        if(p==root||q==root) return root;
 
        TreeNode curLeft=lowestCommonAncestor( root.left, p, q);
        TreeNode curright=lowestCommonAncestor( root.right, p, q);
 
        if(curLeft!=null&&curright==null){
            return curLeft;
        }
        if(curLeft==null&&curright!=null){
            return curright;
        }
        if(curLeft!=null&&curright!=null){
            return root;
        }
        return null;
        
    }
}

先判断是否是空的,再判断是否找到,如果找不到就开始往下递归.,如果一边有一边没有,就返回一边的.如果两边都有,就说明在两边就直接返回这个节点,如果两边都没有,就返回null

递归回来,

递归的思想我觉得就是先大问题,然后通过小问题判断细节,就搞定.

2.思路2

假设这颗二叉树是孩子双亲表示法表示的

因为都知道上一颗连接他的是谁,回溯过去,就跟链表求交点的题目一样的做法

先存储节点的对应的父节点回溯过去存储在相应链表里

但是这道题是孩子表示法表示,并没有双亲节点

因为栈可以依次存储,并先进后出,依次从后往前吐出来

第一步.我们可以用两个栈存储路径

第二步.求栈的大小

第三步,让栈中多的元素出差值个元素

第四步开始出栈,直到栈顶元素相同,此时就是公共祖先,

框架搭好了

但是还是有疑惑.我们如何找根节点到指定节点的路径呢

所以这里我们需要建立一个路径的方法.

这里我的思路就是先判断是否为空,返回假

然后直接把root压入栈内,

然后判断是否为相同,就直接返回真

如果都不相同.就开始找子树或者右树

如果在一个节点的右树找到,那么在他的左树所有压进去的节点都会弹出来.

并会返回false.就开始向上递归.

因为左边没有相同的额节点的时候,就会弹出,每回溯一次都会弹出一次,直到回到那个节点,

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null) return null;
        Stack s1=new Stack<>();
        Stack s2=new Stack<>();
        path(root,p,s1);
        path(root,q,s2);
 
        int size1=s1.size();
        int size2=s2.size();
        int size=0;
        if(size1>size2){
            size=size1-size2;
            while(size!=0){
                s1.pop();
                size--;
            }
        }else{
             size=size2-size1;
            while(size!=0){
                s2.pop();
                size--;
        }
    }
      while(!s1.isEmpty()){
            if(s1.peek()==s2.peek()){
                return s1.peek();
            }
            s1.pop();s2.pop();
        }
       return null;
    }
    boolean path(TreeNode root,TreeNode p,Stack s){
        if(root==null||p==null) return false;
         s.push(root);
        if(root==p) return true;
        boolean flg=path(root.left,p,s);
        if(flg) return true;
        flg=path(root.right,p,s);
        if(flg) return true;
        s.pop();
        return false;
 
    }

四.将二叉搜索树转化为有序链表

我的思路就是一边排序一边修改指向