class Solution {
    public boolean isValid(String s) {
        int[] stack = new int[s.length()];
        int index = 0;
        for(int i = 0;i < s.length();i++){
            char c = s.charAt(i);
            if(index == 0 && (c == ')' || c == ']' || c == '}')){
                return false;
            }
            if(c == '(' || c == '[' || c == '{'){
                stack[index] = s.charAt(i);
                index++;
            }else if(c == ')' && stack[index-1] == '(' || c == ']' && stack[index-1] == '[' || c == '}' && stack[index-1] == '{'){
                index--;
            }else{
                return false;
            }
        }
        if(index == 0){
            return true;
        }else {
            return false;
        }
    }
}

class Solution {
    public int longestValidParentheses(String s) {
        if(s == null || s.length() == 0){
            return 0;
        }
        Stack<Character> stack = new Stack();
        int res = 0,temp = 0;
        int len = s.length();
        int[] arr = new int[len];
        int i = 0;
        while(i < len){
            int size = stack.size();
            if(size == 0){
                stack.push(s.charAt(i));
                arr[i] = 1;
                i++;
                continue;
            }
            if(size > 0 && stack.peek() == '(' && s.charAt(i)==')'){
                stack.pop();
                arr[i] = 0;
                for(int j = i;j >= 0;j--){
                    if(arr[j] == 1){
                        arr[j] = 0;
                        break;
                    }
                }
            }else {
                stack.push(s.charAt(i));
                arr[i] = 1;
            }
            i++;
        }
        for (int j = 0; j < arr.length; j++) {
            if(arr[j] == 0){
               temp++;
               res = res > temp ? res : temp;
            }else {
                temp = 0;
            }
        }
        return res;
    }
}

class Solution {
    public int trap(int[] height) {
        if(height.length <= 1 ){
            return 0;
        }
        int left = 0,right = 0;
        for (int i = 0; i < height.length; i++) {
            if(height[i] > height[left]){
                left = i;
            }
        }
        for (int i = 0; i < height.length; i++) {
            if(height[i] > height[right] && i != left){
                right = i;
            }

        }
        if(left > right){
            right = left + right;
            left = right - left;
            right = right - left;
        }
        return add(left,right,height)+leftsum(0,left,height)+rightsum(right,height.length-1,height);

    }
    public int leftsum(int left,int right,int[] height){
        if(left+1 >= right){
            return 0;
        }
        int index = 0;
        for(int i = 0;i < right;i++){
            if(height[index] < height[i]){
                index = i;
            }
        }
        return add(index,right,height)+leftsum(0,index,height);
    }
    public int rightsum(int left,int right,int[] height){
        if(left+1 >= right){
            return 0;
        }
        int index = left+1;
        for(int i = left+1;i < height.length;i++){
            if(height[index] < height[i]){
                index = i;
            }
        }
        return add(left,index,height)+rightsum(index,right,height);
    }
    public int add(int left,int right,int[] height){
        if(left + 1 >= right){
            return 0;
        }
        int min = Math.min(height[left],height[right]);
        if(min == 0){
            return 0;
        }
        int sum = 0;
        for(int i = left + 1;i < right;i++){
            sum += min - height[i];
        }
        return sum;
    }
}

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        inorder(root,res);
        return res;

    }
    public void inorder(TreeNode root,ArrayList<Integer> res){
        if(root.left != null) {
            inorder(root.left, res);
        }
        res.add(root.val);
        if(root.right != null){
            inorder(root.right,res);
        }
    }
}

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        inorder(root,res);
        return res;
    }
    public void inorder(TreeNode root,ArrayList<Integer> res){
        res.add(root.val);
        if(root.left != null) {
            inorder(root.left, res);
        }
        if(root.right != null){
            inorder(root.right,res);
        }
    }
}

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        inorder(root,res);
        return res;
    }
    public void inorder(TreeNode root,ArrayList<Integer> res){
        if(root.left != null) {
            inorder(root.left, res);
        }
        if(root.right != null){
            inorder(root.right,res);
        }
        res.add(root.val);
    }
}

class BSTIterator {
  // 建立双端队列
    Deque<TreeNode> d = new ArrayDeque<>();
    public BSTIterator(TreeNode root) {
        // 将左节点加入队列中
        dfsLeft(root);
    }
    
    public int next() {
        // 出队
        TreeNode root = d.pollLast();
        int ans = root.val;
        root = root.right;
        dfsLeft(root);
        return ans;
    }

    void dfsLeft(TreeNode root) {
        while (root != null) {
            d.addLast(root);
            root = root.left;
        }
    }
    
    public boolean hasNext() {
        return !d.isEmpty();
    }
}

class Solution {
    ArrayList<TreeNode> list = new ArrayList<>();

	public void flatten(TreeNode root) {
		if (root == null)
			return;
		TreeNode node = root;
		order(root);
		for (int i = 0; i < list.size(); i++) {
			node.left = null;
			node.right = list.get(i);
			node = node.right;
		}
	}

	public void order(TreeNode node) {
		if (node.left != null) {
			list.add(node.left);
			order(node.left);
		}
		if (node.right != null) {
			list.add(node.right);
			order(node.right);
		}
	}
}

class Solution {
    public Node connect(Node root) {
        if(root == null) return null;
		List<Node> list = new ArrayList<Node>();
		list.add(root);
		setNext(list);
		return root;
	}
	
	public void setNext(List<Node> list) {
		if(list.size() == 0) return;
		List<Node> arr = new ArrayList<>();
		for(int i = 0;i < list.size();i++) {
			Node node = list.get(i);
			if(i + 1 < list.size()) {
				node.next = list.get(i + 1);
			}
			if(node.left != null) {
				arr.add(node.left);
			}
			if(node.right != null) {
				arr.add(node.right);
			}
		}
		setNext(arr);
	}
}

class Solution {
    public int evalRPN(String[] tokens) {
		LinkedList<String> list = new LinkedList<>();
		for (String s : tokens) {
			if (s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")) {
				String num1 = list.pollLast();
				String num2 = list.pollLast();
				if (s.equals("+")) {
					list.add(String.valueOf(Integer.valueOf(num2) + Integer.valueOf(num1)));
				} else if (s.equals("-")) {
					list.add(String.valueOf(Integer.valueOf(num2) - Integer.valueOf(num1)));
				} else if (s.equals("*")) {
					list.add(String.valueOf(Integer.valueOf(num2) * Integer.valueOf(num1)));
				} else if (s.equals("/")) {
					list.add(String.valueOf(Integer.valueOf(num2) / Integer.valueOf(num1)));
				}
			} else {
				list.add(s);
			}
		}
		return Integer.valueOf(list.getLast());
	}
}