著书三年倦写字，如今翻书不识志，若知倦书悔前程 ，无如渔樵未识时
给你二叉树的根结点 root ，请你将它展开为一个单链表：
TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
示例 1：
输入：root = [1,2,5,3,4,null,6] 输出：[1,null,2,null,3,null,4,null,5,null,6]
示例 2：
输入：root = [] 输出：[]
示例 3：
输入：root = [0] 输出：[0]
提示：
[0, 2000] 内-100 <= Node.val <= 100
进阶：你可以使用原地算法（O(1) 额外空间）展开这棵树吗？
前序遍历，原地递归修改
按照题意为前序遍历的结果，声明一个TreeNode pre记录前一个访问的节点
这样直接进行前序遍历，把当前节点挂载到pre节点的right上，记得要清除left节点
遍历当前节点的时候left、right节点的值记得先存下来，会在递归的时候被修改掉
class Solution {
/*
1
2 5
3 4 n 6
1
n 2
n 3
n 4
n 5
n 6
*/
TreeNode pre;
public void flatten(TreeNode root) {
dfs(root);
}
public void dfs(TreeNode node){
if (null == node){
return;
}
if (pre!=null){
pre.right = node;
}
pre = node;
TreeNode left = node.left;
TreeNode right = node.right;
node.left = null;
dfs(left);
dfs(right);
}
}输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
参考以下这颗二叉搜索树：
5
/ \
2 6
/ \
1 3
示例 1：
输入: [1,6,3,2,5] 输出: false
示例 2：
输入: [1,3,2,6,5] 输出: true
提示：
数组长度 <= 1000分段验证
分段验证
class Solution {
public boolean verifyPostorder(int[] postorder) {
return validate(postorder,0,postorder.length-1);
}
private boolean validate(int[] postorder, int left ,int right){
//如果左指针大于等于右指针了，说明当前节点以及没有子节点了，自然是符合条件的】
if (left>=right || left < 0 || right < 0) return true;
//找到这段数组对应的根节点，根据后序遍历的特性，即为这段数组的最后一位
int rootNum = postorder[right];
//初始赋值
int leftEnd = -1;
int rightStart = -1;
//开始遍历
for (int i = left; i < right; i++) {
if (postorder[i] < rootNum){
//如果这个值小于根节点的值，说明这个节点应该是在左子树中
leftEnd = i;
}
if (postorder[i] > rootNum && rightStart == -1){
//如果这个值大于根节点的值，说明这个节点应该是右子树上的
//且rightStart == -1 表示是第一次碰到的
rightStart = i;
}
}
//此时如果符合条件的话，应该是 leftEnd 在 rightStart 的左边一位
//或者 没有左子树：leftEnd == -1 且rightStart == left
//或者 没有右子树：rightStart == -1 且leftEnd == right-1
boolean validateResult = (leftEnd>-1 && rightStart> -1 && leftEnd+1== rightStart)
|| ( leftEnd == -1 && rightStart == left )
|| ( rightStart == -1 && leftEnd == right-1);
//自身验证完了，还要对分割好了的子序列的有效性判断
if (validateResult){
return validate( postorder, left, leftEnd ) && validate( postorder, rightStart, right-1 );
}
return false;
}
}给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
示例 1：
输入：s = "(()" 输出：2 解释：最长有效括号子串是 "()"
示例 2：
输入：s = ")()())" 输出：4 解释：最长有效括号子串是 "()()"
示例 3：
输入：s = "" 输出：0
提示：
0 <= s.length <= 3 * 104s[i] 为 '(' 或 ')'栈模拟，java
class Solution {
public int longestValidParentheses(String s) {
Stack<Integer> stack = new Stack<>();
stack.push(-1);
int idx = -1;
int ans = 0;
while (++idx < s.length()) {
//表示上一个未被匹配的左括号'('
if (s.charAt(idx) == '(') {
stack.push(idx);
} else {
//这里是右括号‘)’
stack.pop();
if (!stack.isEmpty()) {
ans = Math.max(ans, idx - stack.peek());
}else{
stack.push(idx);
}
}
}
return ans;
}
}
（的位置给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。
示例 1：
输入：s = "1 + 1" 输出：2
示例 2：
输入：s = " 2-1 + 2 " 输出：3
示例 3：
输入：s = "(1+(4+5+2)-3)+(6+8)" 输出：23
提示：
1 <= s.length <= 3 * 105s 由数字、'+'、'-'、'('、')'、和 ' ' 组成s 表示一个有效的表达式"+(2 + 3)" 无效)"-(2 + 3)" 是有效的)等于把括号去掉算出当前+,-符号真正对应的加减操作算出来
class Solution {
public int calculate(String s) {
int res = 0;
Stack<Integer> stack = new Stack<>();
stack.push(1);
int idx = -1;
int flag = 1;
while (++idx < s.length()){
char c = s.charAt(idx);
if (c == ' ')continue;
switch (c){
case '+':
flag = stack.peek();
break;
case '-':
flag = -stack.peek();
break;
case '(':
stack.push(flag);
break;
case ')':
stack.pop();
break;
default:
//取到整个数字
int num = c - '0';
while (idx+1 < s.length() && s.charAt(idx+1) - '0'>=0 && s.charAt(idx+1)-'9'<=0){
idx++;
num *= 10;
num += s.charAt(idx) - '0';
}
//取到了整个数字
res += flag * num;
break;
}
}
return res;
}
}写出来好像和官方题解一样？
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
示例 1：
输入：head = [1,3,2] 输出：[2,3,1]
限制：
0 <= 链表长度 <= 10000
递归
class Solution {
int[] arr;
public int[] reversePrint(ListNode head) {
recursion(head,0);
return arr;
}
private void recursion(ListNode node, int n) {
if (node==null) {
arr = new int[n];
return;
}
recursion(node.next,n+1);
arr[arr.length-n-1] = node.val;
}
}输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。
示例 1：
输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1] 输出：true 解释：我们可以按以下顺序执行： push(1), push(2), push(3), push(4), pop() -> 4, push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
示例 2：
输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2] 输出：false 解释：1 不能在 2 之前弹出。
提示：
0 <= pushed.length == popped.length <= 10000 <= pushed[i], popped[i] < 1000pushed 是 popped 的排列。注意：本题与主站 946 题相同：https://leetcode-cn.com/problems/validate-stack-sequences/
Java 栈模拟，分步分析理解
直接模拟
Stack，以及两个下标位置标记idxPop，idxPushpushedpopped当前下标的的值一样，如果一样，则说明当前应该进行弹出操作，给stack.pop();同时idxPop++;idxPush++，标记执行到哪一步了idxPop，idxPush这两个指针是否都指向了popped，pushed两个数组的结尾，如果都指向了结尾则表明所有数据都进行过了压入栈操作，同时所有数据都进行了弹出栈操作。class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
Stack<Integer> stack = new Stack<>();
int idxPop = 0;
int idxPush = -1;
while ( ++idxPush < pushed.length){
stack.add(pushed[idxPush]);
while (!stack.isEmpty() && stack.peek() == popped[idxPop]){
idxPop++;
stack.pop();
}
}
return idxPush == pushed.length && idxPop == popped.length;
}
}将一个 二叉搜索树 就地转化为一个 已排序的双向循环链表 。
对于双向循环列表，你可以将左右孩子指针作为双向循环链表的前驱和后继指针，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。
特别地，我们希望可以 就地 完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中最小元素的指针。
示例 1：
输入：root = [4,2,5,1,3] 输出：[1,2,3,4,5] 解释：下图显示了转化后的二叉搜索树，实线表示后继关系，虚线表示前驱关系。
示例 2：
输入：root = [2,1,3] 输出：[1,2,3]
示例 3：
输入：root = [] 输出：[] 解释：输入是空树，所以输出也是空链表。
示例 4：
输入：root = [1] 输出：[1]
提示：
-1000 <= Node.val <= 1000Node.left.val < Node.val < Node.right.valNode.val 的所有值都是独一无二的0 <= Number of Nodes <= 2000二叉搜索树+中序遍历 = 前驱后继关系对应的递增序列
一顿分析
根据题意，要求重新对应前驱后继关系的链表，那么自然想到的就是二叉搜索树的中序遍历操作。
那么我们就在中序遍历的过程中做文章
preNode，当前节点遍历结束的时候，把这个preNode指向到当前节点，这样到下一个节点的时候preNode指向的自然就是中序遍历的前一个节点，也就是当前节点的前驱节点preNode的right指向到当前节点，将当前节点的left指向到preNode，这样就算是完成了链表的基本链接操作tmpNode，将他的right指向到我们在中序遍历过程中遇到的第一个节点，这样head那边的指针关系也关联上了preNode自然就是中序遍历的最后一个节点了，而tmpNode的right又指向了第一个节点，所以我们再在这时候将两者关联起来代码
class Solution {
Node tmpNode = new Node();
Node preNode;
public Node treeToDoublyList(Node root) {
if (null == root){
return null;
}
dfs(root);
preNode.right = tmpNode.right;
tmpNode.right.left = preNode;
return tmpNode.right;
}
public void dfs(Node node){
if (null == node){
return;
}
dfs(node.left);
if (tmpNode.right == null){
//把虚拟头结点连接到最小节点
tmpNode.right = node;
}
if (preNode != null){
//连起来
preNode.right = node;
node.left = preNode;
}
preNode = node;
dfs(node.right);
}
}