本文共 27240 字，大约阅读时间需要 90 分钟。
下面整理一下我在刷剑指offer时，自己做的和网上大神做的各种思路与答案，自己的代码是思路一，保证可以通过，网友的代码提供出处链接。
目录
请实现两个函数，分别用来序列化和反序列化二叉树。
思路一：用一定的规律遍历二叉树例如前序、中序、后序遍历，在遍历过程中将节点的值记录下来，关键是要将每个节点的两个子节点用空点补完整， 在遍历过程中遇到空点也要记录下来，这样再恢复的时候才能还原二叉树的形状。/*class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; }}*/public class Solution { String Serialize(TreeNode root) { if(root==null)return "";//值得注意点1，字符串null和“”的区别 StringBuffer A=new StringBuffer(); S(A,root); return A.toString(); } //本来没想到要在数字和标记b前面加a，但是节点的值一旦大于个位数，这个值转化成字符串后你怎么恢复呢 void S(StringBuffer a,TreeNode t){ //先是节点本身 a.append("a");//分隔符 a.append(String.valueOf(t.val)); //再是它的左节点 if(t.left==null){a.append("ab");}//b前面也要加分隔符 else{S(a,t.left);} //最后是右节点，很明显是前序遍历 if(t.right==null){a.append("ab");} else{S(a,t.right);} } TreeNode Deserialize(String str) { if(str.length()==0)return null;//值得注意点2 String[] ss=str.split("a");//注意“a1a2a3”像这样分割后，ss[0]==""，ss[1]=="1"，一定要注意 TreeNode ROOT=new TreeNode(0); DS(ss,ROOT); return ROOT; } int k=1;//全局变量 String B="b"; void DS(String[] s, TreeNode t){ if(k>=s.length)return;//时刻关注k有没有越界 int temp=Integer.valueOf(s[k]); t.val=temp; k++; if(k>=s.length)return; if(B.equals(s[k])){k++;}//判断字符串内容是否一样，是否是b else{TreeNode tl=new TreeNode(0);t.left=tl;DS(s,tl);} if(k>=s.length)return; if(B.equals(s[k])){k++;} else{TreeNode tr=new TreeNode(0);t.right=tr;DS(s,tr);} }} 需要注意的有，，。
同样是递归，还可以这样写 来自TreeNode Deserialize(String str) { String[] values = str.split(","); Queue queue= new LinkedList ();//用队列代替全局变量下标 for(int i = 0;i != values.length; i ++){ queue.offer(values[i]); } return preOrder(queue); } public TreeNode preOrder(Queue queue){ String value = queue.poll(); if(value.equals("#")){ return null; } TreeNode head = new TreeNode(Integer.valueOf(value)); head.left = preOrder(queue);//递归 head.right = preOrder(queue); return head; } 我们知道，二叉树的遍历，除了用递归实现还可以用栈和队列来实现
来自 用队列实现层序遍历//采用层序遍历public class Solution { String Serialize(TreeNode root) { StringBuilder sb = new StringBuilder(); Queue queue = new LinkedList (); if(root != null) queue.add(root); while(!queue.isEmpty()){ TreeNode node = queue.poll(); if(node != null){ queue.offer(node.left); queue.offer(node.right); sb.append(node.val + ","); }else{ sb.append("#" + ","); } } if(sb.length() != 0) sb.deleteCharAt(sb.length()-1);//将最后一个逗号删掉 return sb.toString(); } TreeNode Deserialize(String str) { TreeNode head = null; if(str == null || str.length() == 0)//上面说过，或的前后不能交换 return head; String[] nodes = str.split(","); TreeNode[] treeNodes = new TreeNode[nodes.length]; for(int i=0; i 用栈实现前序遍历
//前序遍历public class Solution { String Serialize(TreeNode root) { StringBuilder sb = new StringBuilder(); getSerializeString(root, sb); if(sb.length() != 0) sb.deleteCharAt(sb.length()-1);//删除最后的一个逗号 return sb.toString(); } getSerializeString(TreeNode root, StringBuilder sb){ if(root == null) sb.append("#,"); else{ sb.append(root.val + ","); getSerializeString(root.left, sb); getSerializeString(root.right, sb); } } TreeNode Deserialize(String str) { if(str == null || str.length() == 0 || str.length() ==1) return null; String[] nodes = str.split(","); TreeNode[] treeNodes = new TreeNode[nodes.length]; for(int i=0; i stack = new Stack<>(); stack.push(treeNodes[0]); int i = 1; while(treeNodes[i] != null){ //将当前节点赋给栈顶节点的左子，当前节点入栈，下一个节点重复如此操作，直至当前节点为空，则二叉树的最左边一条路到头了 stack.peek().left = treeNodes[i]; stack.push(treeNodes[i++]); } while(!stack.isEmpty()){ //将栈顶节点出栈并给它的右节点赋值 stack.pop().right = treeNodes[++i]; if(treeNodes[i] != null){ //右节点不为空，那右节点还可能有左右子节点 stack.push(treeNodes[i++]);//将右节点入栈 while(treeNodes[i] != null){ //还是上面那一套，一路左左左，直到尽头 stack.peek().left = treeNodes[i]; stack.push(treeNodes[i++]); } } } return treeNodes[0]; }} 请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。
思路一：递归 我的解答通过了牛客网 ，但还是有问题，下面分析其中存在的问题public class Solution { public boolean hasPath(char[] matrix, int rows, int cols, char[] str){ //明明是二维数组，题目传入的却是一维数组，先转化 int count=0; char[][] m=new char[rows][cols]; for(int i=0;i =0&&!f[i][j-1]&&m[i][j-1]==s[k+1]){ if(start(m,f,i,j-1,k+1,s)){ return true;} } if(i-1>=0&&!f[i-1][j]&&m[i-1][j]==s[k+1]){ if(start(m,f,i-1,j,k+1,s)){ return true;} } //f[i][j]=false; //这里掉了，此点不行的话得把标记撤消掉啊，这个代码是有误的，虽然可以通过 return false;//都不满足就说明此点不行，返回上一级 }} 下面的解答，同样还是用的递归，思想一样。
来自public class Solution { public boolean hasPath(char[] matrix, int rows, int cols, char[] str) { int flag[] = new int[matrix.length];//标记数组只需要一个 for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { if (helper(matrix, rows, cols, i, j, str, 0, flag)) return true; } } return false; } private boolean helper(char[] matrix, int rows, int cols, int i, int j, char[] str, int k, int[] flag) { int index = i * cols + j;//免去了新建一个二维数组的空间消耗，做个转换即可 if (i < 0 || i >= rows || j < 0 || j >= cols || matrix[index] != str[k] || flag[index] == 1) return false;//先直观判断此点符合要求吗 if(k == str.length - 1) return true; flag[index] = 1; if (helper(matrix, rows, cols, i - 1, j, str, k + 1, flag) || helper(matrix, rows, cols, i + 1, j, str, k + 1, flag) || helper(matrix, rows, cols, i, j - 1, str, k + 1, flag) || helper(matrix, rows, cols, i, j + 1, str, k + 1, flag)) { return true; } flag[index] = 0;//关键！！！！ return false; }} 思路二：栈
自己写的2.1//2.1import java.util.Stack;public class Solution { public boolean hasPath(char[] matrix, int rows, int cols, char[] str){ boolean[] flag=new boolean[rows*cols]; Stack S=new Stack(); int index,x,y,k=0; boolean l,r,u,d; for(int i=0;i =0&&!flag[index-1]&&matrix[index-1]==str[k+1]; d=x+1 =0&&!flag[index-cols]&&matrix[index-cols]==str[k+1]; //有符合的就入栈 if(r){ S.push(index+1); } if(l){ S.push(index-1); } if(d){ S.push(index+cols); } if(u){ S.push(index-cols); } if(r||l||u||d){ //index周围有点入栈，栈顶对应的str的下标要++，而且说明index这个点目前是合法的，占用了，需要标记一下 k++; flag[index]=true; } else{S.pop();}//index周围没有点符合要求，index无用，需要出栈 } } } } return false; }} 自己写的另一个2.2，与2.1有细微的不同
//2.2while(!S.empty()){ //不知道上一个index有没有把它的四周的点入栈，但是不管有没有入栈，它的flag是true的 index=S.peek();//来看一下栈顶 if(flag[index]){ //栈顶的flag是true，原来上一个index（也是现在这个index）四周没有符合的点，那这个index要出栈，str的下标也要减一 S.pop(); flag[index]=false; k--; continue; } if(++k==str.length)return true;//上一个index四周有符合的点，刚好那是str的最后一个点，结束 flag[index]=true;//目前这个index我先不管它的四周有没有合法的点，先把这个index占用再说 //看看四周情况，符合就入栈 x=index/cols; y=index%cols; r=y+1 =0&&!flag[index-1]&&matrix[index-1]==str[k]; d=x+1 =0&&!flag[index-cols]&&matrix[index-cols]==str[k]; if(r){ S.push(index+1); } if(l){ S.push(index-1); } if(d){ S.push(index+cols); } if(u){ S.push(index-cols); }} 地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？
思路一：每个位置最多四个下一步，找出符合要求的下一步然后递归，标记走过的位置然后避免后来重复计数
非记忆的DFS递归public class Solution { public int movingCount(int threshold, int rows, int cols){ if(threshold<0)return 0;//最开始判断一下 boolean[][] flag=new boolean[rows][cols]; move(flag,0,0,threshold,rows,cols); int count=0; for(int i=0;i =0&&(sum(i)+sum(j-1))<=t&&!f[i][j-1]){move(f,i,j-1,t,rows,cols);} if(i+1 <=t&&!f[i+1][j]){move(f,i+1,j,t,rows,cols);} if(i-1>=0&&(sum(i-1)+sum(j))<=t&&!f[i-1][j]){move(f,i-1,j,t,rows,cols);} } int sum(int x){ //一个数的数位和 int y=0; while(x>0){ y+=x%10; x=x/10; } return y; }} 除了递归DFS，还可以用栈来DFS，还可以用队列来BFS，遍历方法并不唯一。
来自public class Solution { public int movingCount(int threshold, int rows, int cols) { int flag[][] = new int[rows][cols]; //记录是否已经走过 return helper(0, 0, rows, cols, flag, threshold); } private int helper(int i, int j, int rows, int cols, int[][] flag, int threshold) { if (i < 0 || i >= rows || j < 0 || j >= cols || numSum(i) + numSum(j) > threshold || flag[i][j] == 1) return 0; flag[i][j] = 1; return helper(i - 1, j, rows, cols, flag, threshold) + helper(i + 1, j, rows, cols, flag, threshold) + helper(i, j - 1, rows, cols, flag, threshold) + helper(i, j + 1, rows, cols, flag, threshold) + 1; } private int numSum(int i) { int sum = 0; do{ sum += i%10; }while((i = i/10) > 0); return sum; }} 思路二：好好挖掘题目隐含的信息，数位和，表示合法的位置与不合法的位置在一个矩形里面是由一条斜线分割的，那么可以分而治之，将矩形分为好多10*10的矩形，每个矩形，不同矩形的阈值由十位数的数值而改变，统计每个小矩形包含的合法的位置。还有一个关键问题就是，不同矩形的合法点的连通性问题，可以分析，只要矩形的阈值大于等于9，这个矩形包含的合法点是可以通过上下左右运动连接到这个矩形右边和下边的矩形的。
public class Solution { public int movingCount(int threshold, int rows, int cols) { int num=0; int r=f(rows);//找到小矩形个数 int c=f(cols);//找到小矩形个数 int[][] n=new int[r][c];//存放每个小矩形包含的合法点数量 boolean[][] flag=new boolean[r][c];//记录小矩形对其右边和下边的连通性 for(int i=0;i =9){ flag[i][j]=true; if(i+1 上面这段代码其实还有可优化的空间，比如，一、首先判断左上角小矩阵的连通性，没有连通性其他的小矩阵都不用计算了；二、对于10*10的矩阵，不同的阈值其包含合法点的数量是一定的，不用对那些阈值相同的每个10*10的矩阵都计算一遍，但是，边缘部分的非10*10的矩阵就要根据不同阈值每个都要算。
还有，上面代码其实只在所给的大矩阵的行数列数不超过100时才是对的，超过100，阈值还要再减去百位上的数。
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
思路一：注意，是判断是不是子结构，而不是子树，只要B是A的一部分就行。先用层序遍历找到，A中与B的根节点相同的点，然后根据B的结构来一一对应的判断A中对应的是不是与B相同。/**public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; }}*/import java.util.LinkedList;import java.util.Queue;public class Solution { public boolean HasSubtree(TreeNode root1,TreeNode root2) { if(root1==null||root2==null)return false;//先判断，当AB都不为空再进行下面的 boolean flag=false; Queue q=new LinkedList<>(); Queue q2=new LinkedList<>(); Queue q3=new LinkedList<>(); TreeNode t,t2,t3; q.offer(root1); while(!q.isEmpty()){ t=q.poll(); if(t.val==root2.val){ //找到了A中与B的根节点相同的点 flag=false;//设置标志位 q2.offer(t); q3.offer(root2); while(!q3.isEmpty()){ //以B的结构为依据来匹配 t2=q2.poll(); t3=q3.poll(); //点的值不相等 或 B某个点有左子节点但A对应的点没有 或 B某个点有右子节点但A对应的点没有 //跳出循环，继续找A中与B的根节点相同的点（找起点） if((t3.val!=t2.val)||(t2.left==null&&t3.left!=null)||(t2.right==null&&t3.right!=null)){flag=true;break;} //否则，当B的某个点的左右子节点不为空时，A中对应的点的左右子节点也不为空，入队列，层序遍历 if(t3.left!=null){ q2.offer(t2.left); q3.offer(t3.left);} if(t3.right!=null){ q2.offer(t2.right); q3.offer(t3.right);} //若B的某点的左右子节点为空，不管A中对应的这个点有没有左右子节点，也不管A的子节点 } if(!flag){ return true;}//如果不是从上面break出来的，说明匹配成功 //没匹配成功，把两个队列清零，为下次做准备 while(!q2.isEmpty()){q2.remove();} while(!q3.isEmpty()){q3.remove();} } if(t.left!=null){q.offer(t.left);} if(t.right!=null){q.offer(t.right);} } return false; }} 思路二：上面我的解答是利用队列实现层序遍历，有大神的解答用递归来前序遍历
来自public class Solution { public static boolean HasSubtree(TreeNode root1, TreeNode root2) { boolean result = false; //当Tree1和Tree2都不为零的时候，才进行比较。否则直接返回false if (root2 != null && root1 != null) { //如果找到了对应Tree2的根节点的点 if(root1.val == root2.val){ //以这个根节点为为起点判断是否包含Tree2 result = doesTree1HaveTree2(root1,root2); } //如果找不到，那么就再去root的左儿子当作起点，去判断时候包含Tree2 if (!result) { result = HasSubtree(root1.left,root2); } //如果还找不到，那么就再去root的右儿子当作起点，去判断时候包含Tree2 if (!result) { result = HasSubtree(root1.right,root2); } } //返回结果 return result; } public static boolean doesTree1HaveTree2(TreeNode node1, TreeNode node2) { //如果Tree2已经遍历完了都能对应的上，返回true if (node2 == null) { return true; } //如果Tree2还没有遍历完，Tree1却遍历完了。返回false if (node1 == null) { return false; } //如果其中有一个点没有对应上，返回false if (node1.val != node2.val) { return false; } //如果根节点对应的上，那么就分别去子节点里面匹配 return doesTree1HaveTree2(node1.left,node2.left) && doesTree1HaveTree2(node1.right,node2.right); } 还可以这么写
//跟上面其实是一样的，充分利用逻辑连接符号public static boolean HasSubtree(TreeNode root1, TreeNode root2) { if (root1 == NULL || root2 == NULL) return false; return doesTree1HaveTree2(root1, root2) || doesTree1HaveTree2(root1.left, root2) || doesTree1HaveTree2(root1.right, root2);} 还有人想到这种方法：找A与B的前序（或后序、中序）遍历序列，判断B的序列是不是A的子序列，这其实是有问题的，一、是要判断子结构不是子树；二、就算是子序列，仅凭B的一个遍历序列是不能确定B的结构的（可能会有B的序列是A的子序列但B不是A的子树，更别说子结构了）。
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
思路：体会前序遍历与中序遍历是如何确定根节点和其左右节点的，然后对左右节点递归。/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */public class Solution { public TreeNode reConstructBinaryTree(int [] pre,int [] in) { return find(pre,in,0,pre.length-1,0,in.length-1); } TreeNode find(int [] pre,int [] in,int start1,int end1,int start2,int end2){ ////传进来的数组下标是这种情况，说明上一个父节点没有这个子节点，返回空 if(start1>end1||start2>end2){ return null;} int p=0; //在中序遍历中找到前序遍历的第一个点start1，则根节点是start1， //在中序遍历中p的左边是根节点左子树中包含的点，p的右边是根节点右子树中包含的点， //根据左右子树包含的节点个数确定下一阶段pre数组的划分，递归 for(int i=start2;i<=end2;i++){ if(in[i]==pre[start1]){p=i;break;} } TreeNode root=new TreeNode(pre[start1]); root.left=find(pre,in,start1+1,start1+p-start2,start2,p-1); root.right=find(pre,in,start1+1+p-start2,end1,p+1,end2); return root; } } 第一次跟牛客网最高票答案一模一样，哈哈哈！
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes，否则输出No。假设输入的数组的任意两个数字都互不相同。
思路一：二叉搜索树有什么特点，最后一个点是根节点，前面分为分为两段，前面一段全部小于根节点（根节点的左子树），后面一段全部大于根节点（根节点的右子树），也可以只有一段全大的或全小的。对这两段分别递归判断，两段都满足这个特点整个段才返回true。public class Solution { public boolean VerifySquenceOfBST(int [] sequence) { if(sequence.length==0)return false; return f(sequence,0,sequence.length-1); } boolean f(int[] s,int start,int end){ if(start>=end)return true;//这里的等于要不要都可以 int p=end; for(int i=start;i s[end]){ p=i;break; } } //后面一段应该都是大于根节点的，一旦出现有小于的，就不是后序遍历序列 for(int i=p+1;i 递归的方法，最好的时间复杂度是 O(n∗log2n) O ( n ∗ l o g 2 n ) ，最差的是 O(n2) O ( n 2 ) 。
递归还可以这样写 来自class Solution { bool judge(vector & a, int l, int r){ if(l >= r) return true; int i = r; //唯一的区别是这里少用了一个中间变量p while(i > l && a[i - 1] > a[r]) --i; for(int j = i - 1; j >= l; --j) if(a[j] > a[r]) return false; return judge(a, l, i - 1) && (judge(a, i, r - 1)); }public: bool VerifySquenceOfBST(vector a) { if(!a.size()) return false; return judge(a, 0, a.size() - 1); }}; 思路二：不用递归
来自class Solution {public: bool VerifySquenceOfBST(vector sequence) { int size = sequence.size(); if(0==size)return false; int i = 0; while(--size) { while(sequence[i] sequence[size]){i++;} if(i 这种方法在第一个while循环里面显然存在重复的判断，它的时间复杂度始终是 O(n2) O ( n 2 ) ，因此不是一个好方法，只是开拓思路并不推荐。这个方法利用了二叉搜索树的性质，从最后A（根节点为A）每次向前一个，A的右子树根（在序列里面是A前面一个），大于所有A的左子树和自己的左子树，巧的是后序遍历这两个也都放到前面，而自己的大的右子树在后面。
思路一：反转链表，再遍历
/*** public class ListNode {* int val;* ListNode next = null;** ListNode(int val) {* this.val = val;* }* }**/import java.util.ArrayList;public class Solution { public ArrayList printListFromTailToHead(ListNode listNode) { ArrayList A=new ArrayList(); if(listNode==null)return A; ListNode pre=null; ListNode now=listNode; ListNode temp; while(now!=null){ temp=now.next; now.next=pre; pre=now; now=temp; } while(pre!=null){ A.add(pre.val); pre=pre.next; } return A; }} 思路二：递归
来自public class Solution { ArrayList arrayList=new ArrayList ();//类全局变量 public ArrayList printListFromTailToHead(ListNode listNode) { if(listNode!=null){ this.printListFromTailToHead(listNode.next);//这里要不要this都可以，递归调用的方法有返回值但不把它赋给别人也是可以的 arrayList.add(listNode.val); } return arrayList; }} 思路三：用栈来存储节点值，再吐出来就是翻转后的值；或者先直接得到正向序列再反转序列。
给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。
思路一：暴力解法不考虑。用maxIndex记录窗口最大值的位置，用max记录窗口最大值。右移一格，如果maxIndex在窗口里面，就将新加进来的值与它比较，如果右移后maxIndex在窗外，就在窗口中重新找最大值。
import java.util.ArrayList;public class Solution { public ArrayList maxInWindows(int [] num, int size){ ArrayList A=new ArrayList(); if(size<=0)return A; int max=Integer.MIN_VALUE;; int maxIndex=-1; int start=0; for(int end=size-1;end max){ max=num[i];maxIndex=i;} } A.add(max); } else if(max 这种方法时间复杂度跟输入的序列有关，最理想的情况是 O(n) O ( n ) ，最差的情况是 O(n∗m) O ( n ∗ m ) 。
思路二：用最大堆，或PriorityQueue，时间复杂度为 O(n∗log2m) O ( n ∗ l o g 2 m ) 。
来自import java.util.*;public class Solution { public ArrayList maxInWindows(int [] num, int size){ if(num ==null||size <0) return null; ArrayList result = new ArrayList<>(); //防止滑动窗口数值不对 if(size ==0||num.length< size){ return result; } //构造大顶堆 Queue priorityQueue = new PriorityQueue (num.length,new Comparator (){ public int compare(Integer o1, Integer o2) { return o2.compareTo(o1); } }); //先填充size个数值 for(int i=0;i 需要注意的是那个remove方法，。
思想三：这道题可以用双向队列解决(就是头尾都可以push，pop的队列)，时间复杂度 O(n) O ( n ) 。
import java.util.ArrayList;import java.util.ArrayDeque;public class Solution { public ArrayList maxInWindows(int [] num, int size){ ArrayList A=new ArrayList(); if(size<=0)return A; //双向队列，两头都可以进出，存的是数组的下标 ArrayDeque Q = new ArrayDeque(); for(int i=0;i =size-1){ //窗口成型后队列最左边就是最大值的下标 A.add(num[Q.peekFirst()]); } } return A; }} 请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy，则经过替换之后的字符串为We%20Are%20Happy。
思路：如果用API来做，比如replace就是一句话的事，但是这题考的是让你自己写实现。首先考虑替换字符串，是在原来的字符串上做替换，还是新开辟一个字符串做替换。public class Solution { public String replaceSpace(StringBuffer str) { int spacenum = 0;//spacenum为计算空格数 for(int i=0;i =0 && indexold 同样的思路，不同的实现方法
来自class Solution { public: void replaceSpace(char *str,int length) { int count=0; for(int i=0;i =0;i--){ //从后往前 //最后一个空格后面的字符后移2*count，从右到左每遇到一个空格count减一 if(str[i]!=' '){ str[i+2*count]=str[i]; } else{ count--; str[i+2*count]='%'; str[i+2*count+1]='2'; str[i+2*count+2]='0'; } } }}; 思路一：层序遍历一般是遍历到某个点时将其左右节点加入队列，由于隔一行要反转，用栈或者双端队列。
/*public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; }}*/import java.util.ArrayList;import java.util.Stack;public class Solution { public ArrayList > Print(TreeNode pRoot) { ArrayList > A=new ArrayList<>(); if(pRoot==null){ return A; } Stack a1=new Stack(); Stack a2=new Stack(); TreeNode t; a1.push(pRoot); while(!a1.empty()||!a2.empty()) { if(!a1.empty()) { ArrayList A1 = new ArrayList();//每次都新建一个新的，没办法，题目要求返回的是嵌套的 while (!a1.empty()) { t = a1.pop(); A1.add(t.val); if (t.left != null) { a2.add(t.left); } if (t.right != null) { a2.add(t.right); } } A.add(A1); } if(!a2.empty()){ ArrayList A2=new ArrayList(); while (!a2.empty()) { t = a2.pop(); A2.add(t.val); if (t.right != null) { //这里先将右子节点入栈 a1.add(t.right); } if (t.left != null) { a1.add(t.left); } } A.add(A2);} } return A; }} 用双端队列也能实现栈的效果，来自
public class Solution { public ArrayList> Print(TreeNode pRoot) { ArrayList> res = new ArrayList(); if (pRoot == null) return res; Deque deque = new LinkedList();//双端队列 deque.add(pRoot); //由于在一个双端队列里面，不是两个栈，这里需要计数 int curNums = 1; int nextNums = 0; //由于在一个双端队列里面，不是两个栈，还需要反向标志位 boolean flag = true; ArrayList list = new ArrayList(); while(!deque.isEmpty()) { if (flag) { // 右边出，左边进 pRoot= deque.removeLast(); list.add(pRoot.val); curNums--; if (pRoot.left != null) { deque.addFirst(pRoot.left); nextNums++; } if (pRoot.right != null) { deque.addFirst(pRoot.right); nextNums++; } } else { // 左边出，右边进 pRoot= deque.removeFirst(); list.add(pRoot.val); curNums--; if (pRoot.right != null) { deque.addLast(pRoot.right);//这里也是先进右子节点 nextNums++; } if (pRoot.left != null) { deque.addLast(pRoot.left); nextNums++; } } if (curNums == 0) { curNums = nextNums; nextNums = 0; res.add(list); list = new ArrayList();//也是每次新建个新的 flag = !flag;//反向 } } return res; }} 思路二：还是用队列来正常的层序遍历（子节点入队列还是一样的），只是在后面记录点的时候做点手脚
来自//2.1 在出来的时候通过正放倒放达到目的class Solution {public: vector > Print(TreeNode* pRoot) { vector > res; queue Q; if(!pRoot) return res; Q.push(pRoot); bool flag = true; while(!Q.empty()){ int len = Q.size(); vector tmp(len, -1); for(int i = 0; i < len; ++i){ TreeNode *p = Q.front(); Q.pop(); if(p->left) Q.push(p->left); if(p->right) Q.push(p->right); int index = flag ? i : len - 1 - i;//通过标志位在判断应该正着放还是倒着放 tmp[index] = p->val; } flag = !flag; res.push_back(tmp); } return res; } }; 来自
//2.2 同样是正常的层序遍历，对于每层，只是先正着或倒着遍历一遍节点记录下来，再正常的遍历一遍节点将他们的左右子节点入队列public ArrayList> Print(TreeNode pRoot) { ArrayList > ret = new ArrayList<>(); if (pRoot == null) { return ret; } ArrayList list = new ArrayList<>(); LinkedList queue = new LinkedList<>(); queue.addLast(null);//层分隔符 queue.addLast(pRoot); boolean leftToRight = true; while (queue.size() != 1) { TreeNode node = queue.removeFirst(); if (node == null) { //到达层分隔符 Iterator iter = null; if (leftToRight) { iter = queue.iterator();//从前往后遍历 } else { iter = queue.descendingIterator();//从后往前遍历 } leftToRight = !leftToRight; while (iter.hasNext()) { TreeNode temp = (TreeNode)iter.next(); list.add(temp.val); } ret.add(new ArrayList (list)); list.clear(); queue.addLast(null);//添加层分隔符 } else{ if (node.left != null) { queue.addLast(node.left); } if (node.right != null) { queue.addLast(node.right); } } } return ret;}
来自
//2.3 还是正常记录，最后通过中间空间进行反转class Solution {public: vector > Print(TreeNode* pRoot) { vector > res; if(pRoot == NULL) return res; queue que; que.push(pRoot); bool even = false; while(!que.empty()){ vector vec; const int size = que.size(); for(int i=0; i val); if(tmp->left != NULL) que.push(tmp->left); if(tmp->right != NULL) que.push(tmp->right); } if(even) std::reverse(vec.begin(), vec.end()); res.push_back(vec); even = !even; } return res; } }; 对比分析，如果最后我们需要返回的不是一个嵌套结构，就是一个大list。思路一的两个方法仍然可以遍历得到后直接加入list，但思路二的三种方法，要么需要额外的空间（2.1需要额外空间来反着放，2.3需要额外空间来反转，其实都差不多），要么需要额外的时间（2.2对每层的节点都重复遍历了一遍）。这说明根据题目需求，选择合适的数据结构，栈或双端队列，是非常重要的。
转载地址：http://pehci.baihongyu.com/