前言

上次学习了基本的输入输出，现在记录下常用的数据机构。

需要建立二叉树

题目来源
只有学会了建树，才能完成后续的解题方法的研究。

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            int[] arr = new int[n];
            for (int i = 0; i < arr.length; i ++) {
                arr[i] = sc.nextInt();
            }
            TreeNode root = new TreeNode(arr[0]);
            for (int i = 1; i < arr.length; i ++) {
                createBST(root, arr[i]);
            }
            DLR(root);
            System.out.println();
            LDR(root);
            System.out.println();
            LRD(root);
            System.out.println();
        }
    }
    public static void createBST(TreeNode root, int value) {
        if(root.value == value) return;
        if(value < root.value) {
            if(root.left == null) root.left = new TreeNode(value);
            else createBST(root.left, value);
        } else {
            if(root.right == null) root.right = new TreeNode(value);
            else createBST(root.right, value);
        }
    }
    public static void DLR(TreeNode root) {
        if(root != null) {
            System.out.print(root.value + " ");
            DLR(root.left);
            DLR(root.right);
        }
    }
    public static void LDR(TreeNode root) {
        if(root != null) {
            LDR(root.left);
            System.out.print(root.value + " ");
            LDR(root.right);
        }
    }
    public static void LRD(TreeNode root) {
        if(root != null) {
            LRD(root.left);
            LRD(root.right);
            System.out.print(root.value + " ");
        }
    }
    static class TreeNode {
        private int value;
        private TreeNode left;
        private TreeNode right;
        public TreeNode(int value) {
            this.value = value;
        }
    }
}

需要建立链表的时候

题目来源

import java.util.Scanner;

public class Main {
    //定义Node节点
    static class ListNode {
        public int val;
        public ListNode next = null;

        public ListNode(int val) {
            this.val = val;
        }
    }

    public static void main(String[] args) {
        //1.获取输入信息
        Scanner scanner = new Scanner(System.in);
        String string = scanner.nextLine();
        int k = scanner.nextInt();
        String[] strings = string.split(" ");
        //2.创建头结点
        ListNode head = new ListNode(0);
        ListNode tail = head;
        //3.将输入的字符串变为链表节点
        for (String str : strings) {
            ListNode newNode = new ListNode(Integer.valueOf(str));
            tail.next = newNode;
            tail = tail.next;
        }
        head = head.next;
        //每k个反转链表
        ListNode node = reverseGroup(head, k);
        while(node!=null){
            System.out.print(node.val+" ");
            node = node.next;
        }
    }

    //不停地取k个进行翻转，如果不够k个，就直接返回,结束
    public static ListNode reverseGroup(ListNode head, int k) {
        if (head == null || head.next == null || k <= 1)
            return head;
        ListNode currentNode = head;
        //获取k个元素的首尾节点
        for (int count = 1; count < k; count++) {
            currentNode = currentNode.next;
            //不够K个则返回
            if(currentNode==null)
                return head;
        }
        ListNode next = currentNode.next;
        //对局部链表进行反转
        reverse(head,currentNode);
        head.next=reverseGroup(next,k);
        return currentNode;
    }

    //写一个头尾节点反转的局部函数
    public static ListNode reverse(ListNode head, ListNode tail) {
        if (head == null || head.next == null)
            return head;
        ListNode pre = null;
        ListNode next = null;
        while (pre != tail) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }

}