【day10】LeetCode（力扣）刷题(注释详细)[707.设计链表][278.第一个错误的版本][98. 验证二叉搜索树]

class MyLinkedList {
    int size;      //代表链表长度
    ListNode head; //代表头节点

    public MyLinkedList() {
        size = 0;             //新链表长度为0
        head = new ListNode(0);//初始化头节点
    }
    
    public int get(int index) {
        //index不在链表长度范围内，无法找到第index个节点值，返回-1
        if(index < 0 || index >= size) return -1;

        //从头结点开始，遍历index次，返回第index个节点值
        ListNode curr = head;
        for(int i = 0;i <=index;++i){
            curr = curr.next;
        }
        return curr.val;
    }
    
    public void addAtHead(int val) {
        // ListNode curr = head;
        // ListNode add = new ListNode();
        // add.val = val;
        // add.next = curr.next;
        // curr.next = add;
        // ++size;
        addAtIndex(0,val);//调用addAtIndex(index,val)
    }
    
    public void addAtTail(int val) {
        addAtIndex(size,val);//调用addAtIndex(index,val)
    }
    
    public void addAtIndex(int index, int val) {
        //index超出范围直接返回，index小于0则当作0处理
        if(index < 0 || index > size){
            if(index > size)
            return;

            index = 0;
        }

        //插入新节点
        ListNode curr = head;
        for(int i = 0;i < index;++i){
            curr = curr.next;
        }
        ListNode add = new ListNode();
        add.val = val;
        add.next = curr.next;
        curr.next = add;
        ++size;//维护链表长度
    }
    
    public void deleteAtIndex(int index) {
        if(index < 0 || index >= size) return;

        //删除节点
        ListNode curr = head;
        for(int i = 0;i < index;++i){
            curr = curr.next;
        }
        curr.next = curr.next.next;
        size--;//维护链表长度
    }
}

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList obj = new MyLinkedList();
 * int param_1 = obj.get(index);
 * obj.addAtHead(val);
 * obj.addAtTail(val);
 * obj.addAtIndex(index,val);
 * obj.deleteAtIndex(index);
 */

/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int left = 1,right = n;              //确定左右边界，1~n
        int mid;                             //中间版本号

        while(left < right){                 //左右边界还未错位时
            mid = left + ((right-left)>>1);//获取中间值
            
            if(isBadVersion(mid)){
                //若mid不是第一错误版本，第一个错误版本在left与mid-1之间
                right = mid-1;                 
                if(!isBadVersion(right))
                return mid;                    //mid是第一错误版本，直接返回
            }
            else
            left = mid+1;
        }
        //left == right == 第一个错误版本
        return left;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isValidBST(TreeNode root) {
        Deque<TreeNode> dq = new LinkedList<>();//创建栈，拥有元素先进后出的特性
        //记录左孩子的值或左兄弟节点的值，默认为最小值
        double before = -Double.MAX_VALUE;      

        while(!dq.isEmpty() || root != null){
            //利用中序遍历
            while(root != null){//左孩子入栈
                    dq.push(root);
                    root = root.left;
                }

                root = dq.pop();      //从最底层的左孩子开始遍历
                if(root.val <= before){//如果当前节点小于左孩子或左兄弟节点
                    return false;     //不符合搜索树
                }
                before = root.val;    //记录当前值，相当于后出栈元素的左孩子或左兄弟
                root = root.right;    //有兄弟入栈，准备出栈作比较

            }
        return true;
    }
}