Judge sort balanced binary tree of palindrome single – linked list

NC141 judges palindromes

Topic link

1

Use a double pointer and draw the left and right sides close together.

2, code,

import java.util.*;


public class Solution {
    /** * The class name, method name, and parameter name have been specified, do not modify, directly return method specified value **@paramSTR string String Indicates the character string *@returnBool Bool */
    public boolean judge (String str) {
        // write code here
        int l = 0;
        int r = str.length() - 1;
        while(l <= r){
            if(str.charAt(l) ! = str.charAt(r)){return false;
            }
            l++;
            r--;
        }
        return true; }}Copy the code

NC70 single linked list sorting

Topic link

1

There are many ways to solve this problem, and I wrote an insertion sort. Insert each new node into an ordered linked list.

2, code,

import java.util.*;

/* * public class ListNode { * int val; * ListNode next = null; *} * /

public class Solution {
    / * * * *@paramHead ListNode class The head node *@returnListNode class * /
    private void insert(ListNode dummy, ListNode node) {
        ListNode temp = dummy;
        while(temp.next ! =null) {
            if (temp.val <= node.val && node.val <= temp.next.val) {
                node.next = temp.next;
                temp.next = node;
                return;
            }
            temp = temp.next;
        }
        temp.next = node;
    }

    public ListNode sortInList(ListNode head) {
        // write code here
        ListNode dummy = new ListNode(Integer.MIN_VALUE);
        ListNode temp = head;
        while(temp ! =null) {
            ListNode node = temp.next;
            temp.next = null;
            insert(dummy, temp);
            temp = node;
        }
        returndummy.next; }}Copy the code

NC62 balanced binary tree

Topic link

1

First, you define a function to find the height of the tree, and the recursion will work. Second, the height difference between the left subtree and the right subtree is less than 1, and the left subtree and the right subtree are both balanced binary trees, so the tree is a balanced tree.

2, code,

public class Solution {
    private int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftH = getHeight(root.left);
        int rightH = getHeight(root.right);
        return leftH > rightH ? leftH + 1 : rightH + 1;
    }

    public boolean IsBalanced_Solution(TreeNode root) {
        if (root == null) {
            return true;
        }
        int leftH = getHeight(root.left);
        int rightH = getHeight(root.right);
        int gap = leftH > rightH ? leftH - rightH : rightH - leftH;
        if (gap > 1) {
            return false;
        } else {
            returnIsBalanced_Solution(root.right) && IsBalanced_Solution(root.left); }}}Copy the code