二叉搜索树的后续遍历的序列中最后一个数字为根节点，而前面的数字，比根节点小的在左边，比根节点大的在右边。这个左边右边的界限要用一个一个数字和根节点进行比较得出，可能左子树不存在，也有可能右子树不存在。我们循环遍历后序遍历结果的数组，找到比根节点大的第一个点，然后如果这个点后面的数字还有比根节点小的，那么这个后序遍历就不是二叉搜索树的。如果后面没有数字比根节点小，则把左子树和右子树继续进行上述操作，全部操作完成后都满足条件即为二叉搜索树的后序遍历。 public class Solution { public boolean f(int [] sequence, int start, int e...

二叉树的层级遍历。用队列来实现，父节点出队时，把子节点按照先左后右的顺序加到队列中。这样既可完成层级遍历。 import java.util.Queue; import java.util.LinkedList; public class Solution { public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) { ArrayList<Integer> arr = new ArrayList<>(); if(root==null){ return arr; } Queue<Tree...

给出压栈顺序，判断出栈顺序是否合理。维护一个栈，循环遍历出栈顺序，当第i个和栈顶相等时，栈顶弹出，否则进行压栈。当全部都压栈完了之后，栈顶还是和第i个出栈顺序不同，则不合法。如果能循环完，则是合法的。注意栈空的时候 peek会抛异常。 import java.util.ArrayList; import java.util.Stack; public class Solution { public boolean IsPopOrder(int [] pushA,int [] popA) { int l1 = pushA.length; int l2 = popA.length; Stack&l...

O(1)的时间找到栈里的最小值，显然调用函数时是不可能实时从栈里面找的，需要在push()和pop()中处理。我这里选择维护一个minStack，栈顶是最小值。当有元素入栈时，比较该元素与minStack栈顶的大小关系，如果栈顶小于该元素则栈顶出栈存进一个临时栈中，直到找到一个栈顶大于等于该元素，即将该元素push进minStack，然后再把临时栈里的元素放回minStack。当元素出栈是，用同样的方法在minStack中找到该元素，并出栈即可。 其实可以用链表来存大小关系，更加节约内存。 import java.util.Stack; public class Solution { Stac...

螺旋遍历，有四个方向，每个方向坐标的变化是不同的。x或y的加一减一。遇到边界或者遍历过的位置，要变方向。 import java.util.ArrayList; public class Solution { public ArrayList<Integer> printMatrix(int [][] matrix) { int curDirect = 0; int curX = 0; int curY = 0; int h = matrix.length; int w = matrix[0].length; int[][] flag = new int[h][w]; for(in...

实际上就是把每个节点的左右内容互换。递归即可完成。注意判空。 public class Solution { public void Mirror(TreeNode root) { if(root==null){ return; } TreeNode left = root.left; TreeNode right = root.right; root.right = left; root.left = right; if(left!=null){ Mirror(left); } if(right!=null){ Mirror(right); } } }

在root1中存在某一个节点作为根的子树，能包裹住root2。 遍历root1的每一个节点，让每个节点都做根节点，做1中描述的操作。  代码 public class Solution { public boolean isSameTree(TreeNode root1,TreeNode root2){ if(root2==null){ return true; } if(root1==null){ return false; } if(root1.val!=root2.val){ return false; } boolean b1 = isSameTree(root1.left, root...

普通的写法就是把链表存起来，然后反向构造。其实链表翻转就是担心会丢失后面的节点的指针。一共用到了四个指针。三个相邻的节点指针 node1，node2，node3，然后还有一个指针用来存上一轮循环的node2（preNode2）node1的next指向上一轮的node2（preNode2），node2的next指向node1。然后构造下一轮循环参数：preNode2 = node2；node1 = node3；node2 = node1.next；node3 = node2.next；期间还需要判断到哪一个node变为null了，变为null的时候即可返回它的上一个node即为新的头指针。

难点还是怎么把负数转换成补码。先求得负数的绝对值，然后求绝对值的二进制，然后将二进制取反，再加一就是补码了。有方便编程的方法：求得负数绝对值的二进制之后从低位往前数，遇到第一个1之后的所有位都取反即是补码。然后就是进制转换的时候要用long去存int否则会出问题，而且转换成二进制也要补齐32位。貌似python有内置函数。

青蛙一次跳的台阶数可以是1-n中的任意一个，所以在第n个台阶上，他可能是从第n-1和台阶上来的，也可能是从第n-2和台阶上来的，也可能是从第n-3和台阶上来的。。。。。也可能是从第1和台阶上来的，甚至可能是从第0个台阶直接蹦上来的（这样就只有1种跳法）。 所以和上一题不一样的是只加n-1和n-2的了，而是从第n-1一直加到第0个台阶。

青蛙跳第N个台阶的时候，只有可能从两个地方调过来，第N-1号台阶，和第N-2号台阶。所以跳到第N个台阶的可能路径，就是跳到第N-1号台阶，和跳到第N-2号台阶两种方案的和，这就是一个很简单的斐波拉契数列。然后我们做最极端的猜想，当青蛙跳到1号台阶时，一种方案。调到2号台阶两种方案。

确保其中一个栈出栈顺序，与总的进入顺序一致。 队列：先进先出栈：先进后出 那我们可以在入栈的时候，让每次入栈的元素都入到最里面，所以可以在每次入栈的时候，把第一个栈的数据全部转移到第二个栈里面，然后让新来的元素入第一个栈，再把第二个栈的数据转移回来，这样就ok了。

前序，中序，后序，都是指二叉树中，什么时候遍历根节点，左右孩子都是先左后右遍历。 解题的突破口有下面两点1.前序遍历的结果中，根节点肯定是在左右孩子之前的;2.中序遍历的结果中，根节点的左边部分肯定是左子树的，右边部分是右子树的。根据这两点我们可以知道，前序遍历的第一个节点就是根节点。然后再中序遍历中找到这个节点的位置，然后左边的则是左子树，右边的就是右子树。将左右子树用递归的形式进行构建。值得注意的是，找子树的根节点，可以直接比较每一个节点在前序遍历中的位置，位置最靠前的则是子树的根节点。

总体思路：暴力+剪枝坑点：空的二维数组记得判断。因为是有序的，所以每一行的最左边和最右边是可以确定范围的。如果最左边的数字都已经大于目标数字，则该数字不可能存在于接下来的所有行中，直接返回false如果最右边的数字还小于目标数字则直接跳过这一行。遍历每一行时，只有目标数字介于最左边和最右边的数字，才进入这一行进行遍历查找