ARTS_WEEK9

package com.myserious.code.cdz;

/**
 * 641 设计实现双端队列。
 *
 * 你的实现需要支持以下操作：
 * <p>
 * MyCircularDeque(k)：构造函数,双端队列的大小为k。
 * insertFront()：将一个元素添加到双端队列头部。 如果操作成功返回 true。
 * insertLast()：将一个元素添加到双端队列尾部。如果操作成功返回 true。
 * deleteFront()：从双端队列头部删除一个元素。 如果操作成功返回 true。
 * deleteLast()：从双端队列尾部删除一个元素。如果操作成功返回 true。
 * getFront()：从双端队列头部获得一个元素。如果双端队列为空，返回 -1。
 * getRear()：获得双端队列的最后一个元素。 如果双端队列为空，返回 -1。
 * isEmpty()：检查双端队列是否为空。
 * isFull()：检查双端队列是否满了。
 * 示例：
 * <p>
 * MyCircularDeque circularDeque = new MycircularDeque(3); // 设置容量大小为3
 * circularDeque.insertLast(1);			        // 返回 true
 * circularDeque.insertLast(2);			        // 返回 true
 * circularDeque.insertFront(3);			        // 返回 true
 * circularDeque.insertFront(4);			        // 已经满了，返回 false
 * circularDeque.getRear();  				// 返回 2
 * circularDeque.isFull();				        // 返回 true
 * circularDeque.deleteLast();			        // 返回 true
 * circularDeque.insertFront(4);			        // 返回 true
 * circularDeque.getFront();				// 返回 4
 *  
 *  
 * <p>
 * 提示：
 * <p>
 * 所有值的范围为 [1, 1000]
 * 操作次数的范围为 [1, 1000]
 * 请不要使用内置的双端队列库。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/design-circular-deque
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Week9MMyCircularDeque641 {


    /**
     * 错误一 添加时没有考虑到前后连接
     * ["MyCircularDeque","insertFront","getFront","isEmpty","deleteFront","insertLast","getRear","insertLast","insertFront","deleteLast","insertLast","isEmpty"]
     * [[8],[5],[],[],[],[3],[],[7],[7],[],[4],[]]
     * <p>
     * <p>
     * 错误二 队列为空返回-1 注意审题
     * ["MyCircularDeque",
     * "insertFront","deleteLast","getRear",
     * "getFront",
     * "getFront",
     * "deleteFront","insertFront","insertLast",
     * "insertFront","getFront","insertFront"]
     * [[4],[9],[],[],[],[],[],[6],[5],[9],[],[6]]
     *
     * @param args
     */
    public static void main(String[] args) {
        MyCircularDeque deque = new MyCircularDeque(4);

        deque.insertFront(4);
        System.out.println(deque.deleteLast());
        System.out.println(deque.getRear());
        System.out.println(deque.getFront());
        System.out.println(deque.getFront());
        System.out.println(deque.deleteFront());
        deque.insertFront(6);
        deque.insertLast(5);
        deque.insertFront(9);
        System.out.println(deque.getFront());
        deque.insertFront(6);

    }

    /**
     * 链表实现
     * {@link com.myserious.code.cdz.althoughexpand.Week9LoopQueue 使用的是数组实现}
     */
    static class MyCircularDeque {

        private ListNode head;

        private ListNode tail;

        private int size;

        private int len;

        /**
         * Initialize your data structure here. Set the size of the deque to be k.
         */
        public MyCircularDeque(int k) {
            this.size = k;
        }

        /**
         * Adds an item at the front of Deque. Return true if the operation is successful.
         */
        public boolean insertFront(int value) {

            if (isFull()) {
                return false;
            }
            ListNode node = new ListNode(value);
            if (len == 0) {
                head = node;
                tail = node;
            } else {
                head.pre = node;
                node.next = head;
                head = node;
            }
            len++;
            return true;
        }

        /**
         * Adds an item at the rear of Deque. Return true if the operation is successful.
         */
        public boolean insertLast(int value) {

            if (isFull()) return false;

            ListNode node = new ListNode(value);
            if (len == 0) {
                head = node;
                tail = node;
            } else {
                node.pre = tail;
                tail.next = node;
                tail = node;
            }
            len++;
            return true;
        }

        /**
         * Deletes an item from the front of Deque. Return true if the operation is successful.
         */
        public boolean deleteFront() {

            if (isEmpty()) return false;
            if (len == 1) {
                head = null;
                tail = null;
            } else {
                ListNode temp = head;
                head = temp.next;
                temp.next = null;
            }
            len--;
            return true;
        }

        /**
         * Deletes an item from the rear of Deque. Return true if the operation is successful.
         */
        public boolean deleteLast() {

            if (isEmpty()) return false;
            if (len == 1) {
                head = null;
                tail = null;
            } else {
                ListNode temp = tail;
                tail = temp.pre;
                temp.pre = null;
            }
            len--;
            return true;

        }

        /**
         * Get the front item from the deque.
         */
        public int getFront() {
            if (isEmpty()) return -1;
            return head.val;

        }

        /**
         * Get the last item from the deque.
         */
        public int getRear() {
            if (isEmpty()) return -1;
            return tail.val;
        }

        /**
         * Checks whether the circular deque is empty or not.
         */
        public boolean isEmpty() {
            return len == 0;
        }

        /**
         * Checks whether the circular deque is full or not.
         */
        public boolean isFull() {
            return len == size;
        }


        class ListNode {
            int val;
            ListNode pre;
            ListNode next;

            ListNode(int x) {
                val = x;
            }
        }
    }
}

package com.myserious.code.cdz;

import java.util.Arrays;

/**
 *
 * 621. 任务调度器
 *
 * 给定一个用字符数组表示的 CPU 需要执行的任务列表。其中包含使用大写的 A - Z 字母表示的26 种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。CPU 在任何一个单位时间内都可以执行一个任务，或者在待命状态。
 *
 * 然而，两个相同种类的任务之间必须有长度为 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。
 *
 * 你需要计算完成所有任务所需要的最短时间。
 *
 * 示例 1：
 *
 * 输入: tasks = ["A","A","A","B","B","B"], n = 2
 * 输出: 8
 * 执行顺序: A -> B -> (待命) -> A -> B -> (待命) -> A -> B.
 * 注：
 *
 * 任务的总个数为 [1, 10000]。
 * n 的取值范围为 [0, 100]。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/task-scheduler
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Week9MLeastInterval621 {
    public int leastInterval(char[] tasks, int n) {

        int[] count = new int[26];

        //统计 任务出现频率
        for (char task : tasks) {
            count[task-'A']++;
        }

        //升序
        Arrays.sort(count);

        //统计相同 最大频率任务个数
        int maxCountNum = 0;
        for (int i = count.length-1; i > 0; i--) {

            if (count[25]!=count[i]){
                break;
            }
            maxCountNum++;
        }
        //(count[25]-1)*(n+1)+maxCountNum
        //count[25]-1 最大频率，减一的原因是：最后一次单独执行不需要间隔
        //n+1 每个任务之间的间隔加一，其本身不能算数 比如 n=2 ; a -> 间隔 -> 间隔 -> a ，所以将(a -> 间隔 -> 间隔)当做一组
        //最后执行的一组maxCountNum，是频率最高的几个在执行
        //但是还有一种情况是：中间都插满了，但是剩下的频率低的任务没有执行完，这种情况就是 最短执行时间就是任务的数量。
        return Math.max(((count[25]-1)*(n+1)+maxCountNum),tasks.length);
    }
}

package com.myserious.code.cdz;

/**
 * 设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
 * <p>
 * 循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。
 * <p>
 * 你的实现应该支持如下操作：
 * <p>
 * MyCircularQueue(k): 构造器，设置队列长度为 k 。
 * Front: 从队首获取元素。如果队列为空，返回 -1 。
 * Rear: 获取队尾元素。如果队列为空，返回 -1 。
 * enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
 * deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
 * isEmpty(): 检查循环队列是否为空。
 * isFull(): 检查循环队列是否已满。
 *  
 * <p>
 * 示例：
 * <p>
 * MyCircularQueue circularQueue = new MycircularQueue(3); // 设置长度为 3
 * <p>
 * circularQueue.enQueue(1);  // 返回 true
 * <p>
 * circularQueue.enQueue(2);  // 返回 true
 * <p>
 * circularQueue.enQueue(3);  // 返回 true
 * <p>
 * circularQueue.enQueue(4);  // 返回 false，队列已满
 * <p>
 * circularQueue.Rear();  // 返回 3
 * <p>
 * circularQueue.isFull();  // 返回 true
 * <p>
 * circularQueue.deQueue();  // 返回 true
 * <p>
 * circularQueue.enQueue(4);  // 返回 true
 * <p>
 * circularQueue.Rear();  // 返回 4
 *  
 *  
 * <p>
 * 提示：
 * <p>
 * 所有的值都在 0 至 1000 的范围内；
 * 操作数将在 1 至 1000 的范围内；
 * 请不要使用内置的队列库。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/design-circular-queue
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Week9MMyCircularQueue622 {

    class MyCircularQueue {

        private int[] arr;

        private int capacity;

        private int head;

        private int tail;

        /** Initialize your data structure here. Set the size of the queue to be k. */
        public MyCircularQueue(int k) {
            arr = new int[k+1];
            capacity = k+1;
        }

        /** Insert an element into the circular queue. Return true if the operation is successful. */
        public boolean enQueue(int value) {

            if (isFull()){
                return false;
            }
            arr[tail] = value;
            tail = (tail+1)%capacity;
            return true;
        }

        /** Delete an element from the circular queue. Return true if the operation is successful. */
        public boolean deQueue() {

            if (isEmpty()){
                return false;
            }
            head = (head+1)%capacity;
            return true;
        }

        /** Get the front item from the queue. */
        public int Front() {

            if (isEmpty()){
                return -1;
            }
            return arr[head];
        }

        /** Get the last item from the queue. */
        public int Rear() {

            if (isEmpty()){
                return -1;
            }
            //拿出最后一个
            //tail指向的是最后一个的后一位
            //加上capacity的原因防止tail-1为负数的情况
            return arr[(tail-1+capacity)%capacity];
        }

        /** Checks whether the circular queue is empty or not. */
        public boolean isEmpty() {
            return (head-tail)==0;
        }

        /** Checks whether the circular queue is full or not. */
        public boolean isFull() {
            return (tail+1)%capacity==head;
        }
    }
}

package com.myserious.code.cdz;

import java.util.Stack;

/**
 * 938. 二叉搜索树的范围和
 * <p>
 * 给定二叉搜索树的根结点 root，返回 L 和 R（含）之间的所有结点的值的和。
 * <p>
 * 二叉搜索树保证具有唯一的值。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：root = [10,5,15,3,7,null,18], L = 7, R = 15
 * 输出：32
 * 示例 2：
 * <p>
 * 输入：root = [10,5,15,3,7,13,18,1,null,6], L = 6, R = 10
 * 输出：23
 *  
 * <p>
 * 提示：
 * <p>
 * 树中的结点数量最多为 10000 个。
 * 最终的答案保证小于 2^31。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/range-sum-of-bst
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Week9ERangeSumBST938 {


    int ans = 0;
    public int rangeSumBST(TreeNode root, int L, int R) {
        dfs(root, L, R);
        return ans;
    }
    private void dfs(TreeNode root, int L, int R) {
        if (root != null) {
            int val = root.val;
            if (val >= L && val <= R) {
                ans += val;
            }//不能使用else if

            //下面两个判断，是向外扩散着遍历
            if (val > L) {
                dfs(root.left, L, R);
            }
            if (val < R) {
                dfs(root.right, L, R);
            }
        }
    }



    public int rangeSumBST1(TreeNode root, int L, int R) {
        if (root==null) return 0;
        int val = root.val;
        if (val>=L&&val<=R){
            return val+rangeSumBST1(root.left,L,R)+rangeSumBST1(root.right,L,R);
        }else if (val<L){
            return rangeSumBST1(root.right,L,R);
        }else {
            return rangeSumBST1(root.left,L,R);
        }
    }


    /**
     * 方法内部模拟栈的方式 递归
     * @param root
     * @param L
     * @param R
     * @return
     */
    public int rangeSumBST2(TreeNode root, int L, int R) {

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        int res = 0;
        while (!stack.empty()){
            TreeNode pop = stack.pop();
            //注意 自定义栈里的空元素判断
            if (pop!=null){
                int val = pop.val;
                if (val>=L&&val<=R){
                    res+=val;
                    stack.push(pop.left);
                    stack.push(pop.right);
                }else if (val<L){
                    stack.push(pop.right);
                }else {
                    stack.push(pop.left);
                }
            }
        }
        return res;
    }





    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}

package com.myserious.code.cdz;

/**
 * 泰波那契序列 Tn 定义如下： 
 * <p>
 * T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2
 * <p>
 * 给你整数 n，请返回第 n 个泰波那契数 Tn 的值。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：n = 4
 * 输出：4
 * 解释：
 * T_3 = 0 + 1 + 1 = 2
 * T_4 = 1 + 1 + 2 = 4
 * 示例 2：
 * <p>
 * 输入：n = 25
 * 输出：1389537
 *  
 * <p>
 * 提示：
 * <p>
 * 0 <= n <= 37
 * 答案保证是一个 32 位整数，即 answer <= 2^31 - 1。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/n-th-tribonacci-number
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Week9ETribonacci1137 {
    //关键点，使用一个数组保存结果
    //这样才能返回取出
    private int[] nums = new int[38];
    public int tribonacci(int n) {
        if (nums[n]!=0){
            return nums[n];
        }
        if (n==0){
            return 0;
        }else if (n==1||n==2){
            return 1;
        }else {
            //n-1 n-2 n-3 理解是：给出了三个的结果，并且n是从0开始的
            //到这个条件里来就说明n>3
            // 3-1=2; 3-2=1; 3-3=0;
            int res = tribonacci(n - 1) + tribonacci(n - 2) + tribonacci(n - 3);
            nums[n]= res;
            return res;
        }
    }
}

package com.myserious.code.cdz;

import java.util.*;

/**
 * 给定一个二叉搜索树的根结点 root, 返回树中任意两节点的差的最小值。
 * <p>
 * 示例：
 * <p>
 * 输入: root = [4,2,6,1,3,null,null]
 * 输出: 1
 * 解释:
 * 注意，root是树结点对象(TreeNode object)，而不是数组。
 * <p>
 * 给定的树 [4,2,6,1,3,null,null] 可表示为下图:
 * <p>
 * 4
 * /   \
 * 2      6
 * / \
 * 1   3
 * <p>
 * 最小的差值是 1, 它是节点1和节点2的差值, 也是节点3和节点2的差值。
 * 注意：
 * <p>
 * 二叉树的大小范围在 2 到 100。
 * 二叉树总是有效的，每个节点的值都是整数，且不重复。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Week9EMinDiffInBST783 {

    /**
     * 时间复杂度为 O(nlg(n))
     * 原因：分析
     * dfs函数调用的时间复杂度为 n
     * for循环时间复杂度也为 n
     * 而还有使用到了一个内置的排序功能 时间复杂度为 nlgn
     * 所以整体的时间复杂度为 O（n+n+nlgn）简约为 O(nlgn)
     */
    private List<Integer> values = new ArrayList<>();
    public int minDiffInBST(TreeNode root) {
        dfs(root);
        values.sort(null);
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < values.size()-1; i++) {
            ans = Math.min(ans,values.get(i+1)-values.get(i));
        }
        return ans;
    }

    private void dfs(TreeNode root) {
        if (root==null) return;

        values.add(root.val);
        dfs(root.right);
        dfs(root.left);
    }


    /**
     * 方法二：中序遍历，直接算出结果
     * 时间复杂度为O(N) N节点数量
     * 空间复杂度O(H) H为树的高度
     *
     * 时间复杂度好理解，inorder中的 的代码运行次数
     * 空间复杂度为：方法调用栈的大小
     *
     * 为什么栈的大小是 树的高度H而不是节点数量N？
     * 原因：
     * 首先这是一个平衡二叉树，第一个递归调用，栈的空间耗费了H空间，并且释放
     * 第二次递归调用，又是耗费了H的空间，然后释放，所以是H空间。
     */
    private TreeNode pre;
    private int ans = Integer.MAX_VALUE;
    public int minDiffInBST1(TreeNode root) {
        inorder(root);
        return ans;
    }

    /**
     * 二叉搜索树的中序遍历是有序递增序列
     * @param root
     */
    private void inorder(TreeNode root) {
        if (root==null)return;
        inorder(root.left);
        if (pre!=null){
            ans =Math.min(ans,root.val -pre.val) ;
        }
        //每次计算完都需要赋值
        pre = root;
        inorder(root.right);
        System.out.println();
    }

    //思路正确，方法错误，
    // 重点在：任意两个节点
    // 将所有节点元素拿出，然后进行排序，然后前后相减，得到所有的差值
    // 拿出最小的那个差值即可
//    private void bst(TreeNode root) {
//        TreeNode left = root.left;
//        TreeNode right = root.right;
//        int a= 0;
//        if (left!=null&&right!=null){
//            a = Math.min(Math.abs(left.val-root.val),Math.abs(right.val-root.val));
//        }else if (left!=null){
//            a = Math.abs(left.val-root.val);
//        }else if (right!=null){
//            a = Math.abs(right.val-root.val);
//        }else {
//            return;
//        }
//        mixList.sort(Comparator.comparingInt(Integer::intValue));
//        mixList.add(a);
//        bst(root.left);
//        bst(root.right);
//    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}

package com.myserious.code.cdz;

/**
 *
 * 687. 最长同值路径
 * 给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。
 * <p>
 * 注意：两个节点之间的路径长度由它们之间的边数表示。
 * <p>
 * 示例 1:
 * <p>
 * 输入:
 * <p>
 * 5
 * / \
 * 4   5
 * / \   \
 * 1   1   5
 * 输出:
 * <p>
 * 2
 * 示例 2:
 * <p>
 * 输入:
 * <p>
 * 1
 * / \
 * 4   5
 * / \   \
 * 4   4   5
 * 输出:
 * <p>
 * 2
 * 注意: 给定的二叉树不超过10000个结点。 树的高度不超过1000。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/longest-univalue-path
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Week9ELongestUnivaluePath687 {

    private int ans;
    /**
     * 题目看懂很重要
     * 根本没有看懂题目，
     * 办法：去网上看视频
     * @param root
     * @return
     */
    public int longestUnivaluePath(TreeNode root) {
        arrowLength(root);
        return ans;
    }

    private int arrowLength(TreeNode node) {

        if (node==null)return 0;

        int left = arrowLength(node.left);
        int right = arrowLength(node.right);


        //为什么不能直接返回left 与right的值
        //这里可以想象，递归是将问题简化为最小的一次单位
        //也就是说，只统计node这一个节点的相同子节点
        //如果这一次node.val!=node.left.val&&node.val!=node.right.val
        //那么其 left与right下面所有所统计的相同节点数量都是无效的，所以必须为0！
//        if (node.left!=null&&node.val==node.left.val) left++;
//        if (node.right!=null&&node.val==node.right.val) right++;

        left = (node.left!=null&&node.val==node.left.val)? left+1:0;
        right =(node.right!=null&&node.val==node.right.val)?right+1:0;
        ans = Math.max(ans,left+right);
        return Math.max(left,right);
    }


    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}

package com.myserious.code.cdz;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

/**
 * 894. 所有可能的满二叉树
 * 满二叉树是一类二叉树，其中每个结点恰好有 0 或 2 个子结点。
 * <p>
 * 返回包含 N 个结点的所有可能满二叉树的列表。 答案的每个元素都是一个可能树的根结点。
 * <p>
 * 答案中每个树的每个结点都必须有 node.val=0。
 * <p>
 * 你可以按任何顺序返回树的最终列表。
 * <p>
 *  
 * <p>
 * 示例：
 * <p>
 * 输入：7
 * 输出：[[0,0,0,null,null,0,0,null,null,0,0],[0,0,0,null,null,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,null,null,null,null,0,0],[0,0,0,0,0,null,null,0,0]]
 * 解释：
 * <p>
 *  
 * <p>
 * 提示：
 * <p>
 * 1 <= N <= 20
 * 在真实的面试中遇到过这道题？
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/all-possible-full-binary-trees
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Week9MAllPossibleFBT894 {
    private Map<Integer,List<TreeNode>> memo = new HashMap<>();
    public List<TreeNode> allPossibleFBT(int N) {
        if (!memo.containsKey(N)){
            List<TreeNode> ans = new LinkedList<>();
            if (N==1){
                TreeNode treeNode = new TreeNode(0);
                ans.add(treeNode);
            }else if (N%2==1){
                //奇数才有满二叉树
                //为什么i不能等于N
                //不能等于N的原因：
                //一个节点必须 有左右子节点 或者没有
                //当i=N时 root节点不满足left和right都有值
                for (int i = 1; i < N; i+=2) {
                    for (TreeNode left :allPossibleFBT(i)){
                        for (TreeNode right :allPossibleFBT(N-i-1)){
                            TreeNode root = new TreeNode(0);
                            root.left = left;
                            root.right = right;
                            ans.add(root);
                        }
                    }
                }
            }
            memo.put(N,ans);
        }
        return memo.get(N);
    }

    public static void main(String[] args) {
        for (int i = 1; i < 21; i+=2) {
            System.out.println(i);
        }
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}

class VolatileExample {
    int x = 0;
    volatile boolean v = false;


    public void writer() {
        x = 42;
        v = true;
    }


    public void reader() {
        if (v == true) { // 这里x会是多少呢？ } }}
            System.out.println("x="+x);
        }
    }
}