[面经]CVTE的两道笔试编程题

痛定思痛。 2022-07-29 10:38 242阅读 0赞

<table> 
 <tbody> 
 <tr> 
 <td><a href="http://blog.csdn.net/kesarchen/article/details/50811228" rel="nofollow">[面经]CVTE的两道笔试编程题</a></td> 
 </tr> 
 <tr> 
 <td> 
 <blockquote> 
 晚上状态有点不好，然后就仓促参加笔试了。前面很多道选择题，真是坑，都是多选（混杂了多道单选）。下面就说说笔试题的两道编程题吧。其实我做的时候也是挺紧张的，随意符合题意的做完提交，也没加以优化，其实如果时间允许，我也是蛮想优化下的，不过这 场笔试不是看你优化得有多好，而是看你做对了没。 
 </blockquote> <h3>第一道题：字符数组的循环右移问题</h3> 
 <blockquote> 
 题目要求：将N个字符的数组，循环右移K位。时间复杂度O(N)。 现场思路： 1. k可以小于N，大于N，等于N，按照这几种请况分析。首先我们必须知道，当N=dK（d=0,1,2..）时，字符数组循环右移后，字符数组中字符位置不变。有了这个“突破口”我们就能将K&gt;N转化成K&lt;=N来解，这样缩小了判断的范围。 2. 接下来我们只需要分析K 
 </blockquote> <pre><code>public static void solution(int[] arr, int length, int shiftStep)
{
 if(arr==null||length==0) return;
 int count=shiftStep%length;
 if(count==0) return;
 int[] copy=new int[length];
 for(int i=0;i&lt;length;i++){
 copy[i]=arr[i];
 }
 for(int i=0;i&lt;length;i++){
 arr[(i+count)%length]=copy[i];
 }
}</code></pre> <h3>第二道题：字符串去重问题</h3> 
 <blockquote> 
 题目要求：删除小写字母字符串中重复字符。如果可以，优先删除重复字符中排在比他小字符前面的字符。 比如，输入：bbcacdww；输出：bacdw 现场思路：一开始，我本来在想这个问题的最优解，排除使用“暴破”。想了一阵子，可能是太紧张了，思路不开。时间快到了，被迫是用“暴破”。然而“暴破”也不是那么容易的，orz。 
 </blockquote> <pre><code>public static String solution(String s)
{
 if(s==null||"".equals(s)) return s;

StringBuilder sb = new StringBuilder(s);
 int i = 0;
 while (i &lt; sb.length())
 {
 char temp = sb.charAt(i);
 boolean isR = false; // 是否有重复的字符在i的前面
 boolean isFront = true; // 要删除后面的重复字符?true删除后面的重复字符:false删除前面的重复字符
 int j = i + 1;
 while (j &lt; sb.length())
 {
 if (isFront &amp;&amp; sb.charAt(j) &lt; temp)
 {
 isFront = false;
 }
 if (sb.charAt(j) == temp)
 {
 if (isFront)
 {
 sb.deleteCharAt(j);
 continue;
 }
 else
 {
 isR = true;
 }
 }
 j++;
 }
 if (isR)
 {
 sb.deleteCharAt(i);
 }
 else
 {
 i++;
 }
 }
 return sb.toString();
}</code></pre> 
 <blockquote> 
 总结： 算法题还是要有针对性的刷题，然后从中提取解法和经验。 
 </blockquote> 
 <div>
 作者：KesarChen 发表于2016/3/5 22:49:15 
 <a href="http://blog.csdn.net/kesarchen/article/details/50811228" rel="nofollow"> 原文链接</a> 
 </div> 
 <div>
 阅读：868 评论：0 
 <a href="http://blog.csdn.net/kesarchen/article/details/50811228#comments" rel="nofollow"> 查看评论</a> 
 </div> </td> 
 </tr> 
 <tr> 
 <td>&nbsp;</td> 
 </tr> 
 <tr> 
 <td><a href="http://blog.csdn.net/kesarchen/article/details/50698268" rel="nofollow">[算法学习]8皇后问题</a></td> 
 </tr> 
 <tr> 
 <td> 
 <blockquote> 
 问题描述： 国际象棋的“8皇后问题”：在8x8的国际象棋上摆放8个皇后，使其不能互相攻击，即8个皇后中任意两个不得处在同一行、同一列或同一对角线上。共有多少种符合条件的摆法？ 解法与分析： 1. 首先是不能同一列同一行，那么每个皇后必须各独占一行一列，使用二维数组来描述就有点浪费空间了。这里我们使用一个8个元素的一维数组来表示每个皇后的每一行。 2. 那么独占一列的情况，描述起来就像是实现{0,1,2,3,4,5,6,7}这个一维数组的全排列。 3. 最后要解决的是不能在同一对角线的判断：假设两个数载一维数组nums位置i，j，那么i，j在同一对角线的条件是 i-j = nums[i]-nums[j] || j-i = nums[i]-nums[j]。 
 </blockquote> 
 <hr> <h2>参考代码如下</h2> <pre><code>/** * @Description: 打印所有"8皇后"的可能位置 * @param * @return void */
public static void eightQueen()
{
 int[] queens = { 0, 1, 2, 3, 4, 5, 6, 7};
 getAllArrange(queens, 0, queens.length - 1);
}

/** * @Description: 数组全排列筛选 * @param @param nums * @return void */
private static void getAllArrange(int[] nums, int start, int end)
{
 if (start &gt; end)
 {
 System.out.println(Arrays.toString(nums));
 return;
 }
 boolean isContinue = false;
 for (int i = start; i &lt;= end; isContinue=false,i++)
 {
 exch(nums, start, i);
 for (int a = start - 1; a &gt;= 0; a--)
 {
 if (isDiagonal(nums, a, start))
 {
 exch(nums, start, i);
 isContinue=true;
 break;
 }
 }
 if(isContinue)
 {
 continue;
 }
 getAllArrange(nums, start + 1, end);
 exch(nums, start, i);
 }
}

/** * * @Description: 判断两个位置是否在同一对角线上 * @param @param nums * @param @param i * @param @param j * @param @return * @return boolean */
private static boolean isDiagonal(int[] nums, int i, int j)
{
 int result = nums[i] - nums[j];
 return (i - j) == result || (j - i) == result;
}

/** * * @Description: 交换数组中的两个数的值 * @param @param nums * @param @param i * @param @param j * @return void */
private static void exch(int[] nums, int i, int j)
{
 if (i == j)
 return;
 nums[i] ^= nums[j];
 nums[j] ^= nums[i];
 nums[i] ^= nums[j];
}</code></pre> 
 <ul> 
 <li>附：<a href="https://github.com/ClaymanTwinkle/SwordTest/blob/master/src/array/EightQueen.java" rel="nofollow">源码地址</a> </li> 
 </ul> 
 <div>
 作者：KesarChen 发表于2016/2/19 15:21:16 
 <a href="http://blog.csdn.net/kesarchen/article/details/50698268" rel="nofollow"> 原文链接</a> 
 </div> 
 <div>
 阅读：5021 评论：0 
 <a href="http://blog.csdn.net/kesarchen/article/details/50698268#comments" rel="nofollow"> 查看评论</a> 
 </div> </td> 
 </tr> 
 <tr> 
 <td>&nbsp;</td> 
 </tr> 
 <tr> 
 <td><a href="http://blog.csdn.net/kesarchen/article/details/50685651" rel="nofollow">[算法学习]Java实现字符序列全组合</a></td> 
 </tr> 
 <tr> 
 <td> 
 <blockquote> 
 问题描述： 假设数组中字符无重复，输入一个字符数组，打印出字符的全部组合。例如：输入{a,b,c}输出a、b、c、ab、ac、bc、abc 
 解法与分析： 不使用辅助空间。输入一组n个字符的数组，将打印出C(1,n)+…+C(n,n)=2^n个组合。 1.按照从1到n作为一个循环，每次输出C(i,n)个组合。这样，我们只需要处理如何输出一个C(i,n)就可以解决问题。 2.处理C(i,n)：i有两种特殊情况，一种是i=1，那么直接输出n个字符中每个字符就可以；一种是i=n，那么整个字符数组一起输出就可以。i&gt;1&amp;&amp;i 
 </blockquote> <h2>参考代码如下</h2> <pre><code>/** * 从C(1,n)计算到C(n,n)，时间复杂度是C(1,n)+...+C(n,n)=O(2^n) * 应该有不用递归的更优解法吧，但是我一时也想不过来，只能用递归来解。 * @param cs */
public static void printAllSeqCombination(char[] cs)
{
 if (cs == null || cs.length == 0)
 return;
 for (int i = 1; i &lt;= cs.length; i++)
 {
 printAllSeqCombination(cs, 0, cs.length - 1, 0, i - 1);
 }
}

/** * * @param cs * @param array_start 能被组合的数组元素开始第一个元素 * @param array_end 能被组合的数组元素最后一个元素 * @param print_start 要被打印出来的第一个index * @param print_end 要被打印出来的最后一个一个index */
private static void printAllSeqCombination(char[] cs, int array_start,int array_end, int print_start, int print_end)
{
 if (print_end == array_end)
 {
 System.out.println(new String(cs, print_start, print_end- print_start + 1));
 return;
 }
 if (array_start == print_end)
 {
 for (int i = array_start; i &lt;= array_end; i++)
 {
 exch(cs, array_start, i);
 System.out.println(new String(cs, print_start, print_end- print_start + 1));
 exch(cs, array_start, i);
 }
 return;
 }
 while (print_end&lt;=array_end)
 {
 printAllSeqCombination(cs, ++array_start, array_end, print_start++, print_end++);
 }
}
/** * * @Description: 交换数组中两个数的值 * @param @param cs * @param @param i * @param @param j * @return void * @throws */
private static void exch(char[] cs, int i, int j)
{
 if (i == j)
 return;
 char temp = cs[i];
 cs[i] = cs[j];
 cs[j] = temp;
}</code></pre> 
 <ul> 
 <li>附：<a href="https://github.com/ClaymanTwinkle/SwordTest/blob/master/src/array/AllSeqCombination.java" rel="nofollow">源码地址</a> </li> 
 </ul> 
 <div>
 作者：KesarChen 发表于2016/2/18 14:00:31 
 <a href="http://blog.csdn.net/kesarchen/article/details/50685651" rel="nofollow"> 原文链接</a> 
 </div> 
 <div>
 阅读：5008 评论：0 
 <a href="http://blog.csdn.net/kesarchen/article/details/50685651#comments" rel="nofollow"> 查看评论</a> 
 </div> </td> 
 </tr> 
 <tr> 
 <td>&nbsp;</td> 
 </tr> 
 <tr> 
 <td><a href="http://blog.csdn.net/kesarchen/article/details/50685646" rel="nofollow">[算法学习]整数序列的奇偶分类</a></td> 
 </tr> 
 <tr> 
 <td> 
 <blockquote> 
 问题描述： 输入一组序列，奇数在前，偶数在后，输出整理后的序列。 
 解法与分析： 能马上想到用二分法，就很快能解决问题。 
 </blockquote> 
 <hr> <h2>参考代码如下</h2> <pre><code>/** * 解法：使用二分法 * @param nums */
public static void reorderOddEven(int[] nums)
{
 if(nums==null)
 {
 return;
 }
 int left=0;
 int right=nums.length-1;
 while (left&lt;right)
 {
 while (left&lt;right&amp;&amp;nums[left]%2==1)
 {
 left++;
 }
 while (left&lt;right&amp;&amp;nums[right]%2==0)
 {
 right--;
 }
 if(left&gt;=right)
 {
 break;
 }
 exch(nums, left, right);
 }
}

/** * * @Description: 交换数组中两个数的值 * @param @param nums * @param @param index1 * @param @param index2 * @return void */
private static void exch(int[] nums,int index1,int index2)
{
 if(index1==index2)
 {
 return;
 }
 nums[index1]^=nums[index2];
 nums[index2]^=nums[index1];
 nums[index1]^=nums[index2];
}</code></pre> 
 <ul> 
 <li>附：<a href="https://github.com/ClaymanTwinkle/SwordTest/blob/master/src/array/OddEven.java" rel="nofollow">源码地址</a> </li> 
 </ul> 
 <div>
 作者：KesarChen 发表于2016/2/18 13:59:51 
 <a href="http://blog.csdn.net/kesarchen/article/details/50685646" rel="nofollow"> 原文链接</a> 
 </div> 
 <div>
 阅读：4973 评论：0 
 <a href="http://blog.csdn.net/kesarchen/article/details/50685646#comments" rel="nofollow"> 查看评论</a> 
 </div> </td> 
 </tr> 
 <tr> 
 <td>&nbsp;</td> 
 </tr> 
 <tr> 
 <td><a href="http://blog.csdn.net/kesarchen/article/details/50685640" rel="nofollow">[算法学习]顺时针打印矩阵</a></td> 
 </tr> 
 <tr> 
 <td> 
 <blockquote> 
 问题描述： 顺时针打印矩阵 例如： { {1,2,3,4}, {5,6,7,8}, {9,10,11,12}, {13,14,15,16} } 打印结果：1、2、3、4、8、12、16、15、14、13、9、5、6、7、11、10 
 解法与分析： 考虑几个特殊情况：行1列n，行n列1，行1列1。考虑到这几个后其实就不难了。 
 </blockquote> 
 <hr> <h2>参考代码如下</h2> <pre><code>/** * 顺时针打印矩阵 * * @param matrix */
public static void clockwisePrintMatrix(int[][] matrix)
{
 // 1.test代码
 if (matrix == null)
 {
 System.err.println("输入矩阵有误");
 return;
 }
 int hight = matrix.length;
 if (hight == 0)
 {
 System.err.println("输入矩阵有误");
 return;
 }
 int width = matrix[0].length;
 for (int i = 1; i &lt; hight; i++)
 {
 if (matrix[i].length != width)
 {
 System.err.println("输入矩阵有误");
 return;
 }
 }
 if (width == 0)
 {
 System.err.println("输入矩阵有误");
 return;
 }

// 2.核心代码
 int loopNum = width &gt; hight ? (hight + 1) / 2 : (width + 1) / 2;

printMatrix(matrix, 0, 0, width, hight);
 for (int i = 1; i &lt; loopNum; i++)
 {
 printMatrix(matrix, i, i, width - 2, hight - 2);
 }
 System.out.println();
}

/** * 顺时针打印一圈矩阵 * * @param matrix * @param x * @param y * @param xLen * @param yLen */
private static void printMatrix(int[][] matrix, int x, int y, int xLen, int yLen)
{
 for (int i = 0; i &lt; xLen; i++)
 {
 System.out.print(matrix[y][x + i] + ",");
 }
 for (int i = 1; i &lt; yLen; i++)
 {
 System.out.print(matrix[y + i][x + xLen-1] + ",");
 }
 for (int i = 2; i &lt;=xLen&amp;&amp;yLen!=1; i++)
 {
 System.out.print(matrix[y + yLen-1][x + xLen - i] + ",");
 }
 for (int i = 2; i &lt;yLen&amp;&amp;xLen!=1; i++)
 {
 System.out.print(matrix[y + yLen - i][x] + ",");
 }
}</code></pre> 
 <ul> 
 <li>附：<a href="https://github.com/ClaymanTwinkle/SwordTest/blob/master/src/array/PrintMatrix.java" rel="nofollow">源码地址</a> </li> 
 </ul> 
 <div>
 作者：KesarChen 发表于2016/2/18 13:59:02 
 <a href="http://blog.csdn.net/kesarchen/article/details/50685640" rel="nofollow"> 原文链接</a> 
 </div> 
 <div>
 阅读：4734 评论：0 
 <a href="http://blog.csdn.net/kesarchen/article/details/50685640#comments" rel="nofollow"> 查看评论</a> 
 </div> </td> 
 </tr> 
 <tr> 
 <td>&nbsp;</td> 
 </tr> 
 <tr> 
 <td><a href="http://blog.csdn.net/kesarchen/article/details/50685632" rel="nofollow">[算法学习]数组的旋转</a></td> 
 </tr> 
 <tr> 
 <td> 
 <blockquote> 
 问题描述： 返回将一维数组向右旋转k个位置的结果。 比如，一维数组{1,2,3,4,5}，k=2时，返回结果是{4,5,1,2,3}。 要求常数级空间复杂度，允许修改原有数组。 
 解法与分析： 使用三旋转：全部旋转一次，前面0到k-1旋转一次，后面k到数组最后一个数旋转一次，就可以解决问题。 
 </blockquote> 
 <hr> <h2>参考代码如下</h2> <pre><code>public static int[] rotateK(int[] datas,int k)
{
 reverse(datas, 0, datas.length-1);
 reverse(datas, 0, k-1);
 reverse(datas,k,datas.length-1);
 return datas;
}

/** * 反转start和end之间的数 * @param datas * @param start * @param end */
public static void reverse(int[] datas,int start,int end)
{
 while(start&lt;end)
 {
 // 交换两个数的值
 datas[start]^=datas[end];
 datas[end]^=datas[start];
 datas[start]^=datas[end];
 start++;
 end--;
 }
}</code></pre> 
 <ul> 
 <li>附：<a href="https://github.com/ClaymanTwinkle/SwordTest/blob/master/src/array/Rotate.java" rel="nofollow">源码地址</a> </li> 
 </ul> 
 <div>
 作者：KesarChen 发表于2016/2/18 13:58:13 
 <a href="http://blog.csdn.net/kesarchen/article/details/50685632" rel="nofollow"> 原文链接</a> 
 </div> 
 <div>
 阅读：5039 评论：0 
 <a href="http://blog.csdn.net/kesarchen/article/details/50685632#comments" rel="nofollow"> 查看评论</a> 
 </div> </td> 
 </tr> 
 <tr> 
 <td>&nbsp;</td> 
 </tr> 
 <tr> 
 <td><a href="http://blog.csdn.net/kesarchen/article/details/50685624" rel="nofollow">[算法学习]二维数组的查找</a></td> 
 </tr> 
 <tr> 
 <td> 
 <blockquote> 
 问题描述： 二维数组中的查找。在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样一个二维数组和一个整数，判断数组中是否包含该整数。 例如： { {1,2,3,4} {2,4,6,7} {4,5,7,8} {6,7,8,9} } 
 解法与分析： 可以使用二分法来查找。 1. 从四个角中找一个起点，向列走是递增&amp;向行走是递减，或者，向列走是递减&amp;向行走是递增。符合这个条件的只有左下角和右上角。 2. 以左下角为例，定义两个指针，一个向上走（减），一个向右走（增）。 3. 如何走？判断当前两个指针所指向二维数组中的值比搜索值大还是小，比搜索值大的话，向上走，比搜索值小的话，向右走。直到两个指针都停止不能走为止。 
 </blockquote> 
 <hr> <h2>参考代码如下</h2> <pre><code>/** * 查找。我们从二维数组左下角找起会很快。(以下计算过程画个二维数组图，然后一行一行代码看会很容易理解的) * @param nums 二维数组 * @param target 目标整数 * @param column 取小列 * @param row 取最大行 * @return */
public static boolean findNum(int[][] nums,int target,int column,int row)
{
 if(nums==null)
 {
 // 防止 null异常
 return false;
 }
 while (column&gt;0&amp;&amp;row&gt;0)
 {
 int current=nums[row-1][column-1]; //当前值

if(current&gt;target)
 {
 // 当前值太大，缩行(向上面一行走,因为上面一行值会小一点)
 --row;
 }
 else if(current&lt;target)
 {
 // 当前值太小，缩列(向右边一列走,因为右边一列值会大一点)
 ++column;
 }
 else
 {
 // 找到值
 return true;
 }
 }

return false;
}</code></pre> 
 <ul> 
 <li>附：<a href="https://github.com/ClaymanTwinkle/SwordTest/blob/master/src/array/TwoDArray.java" rel="nofollow">源码地址</a> </li> 
 </ul> 
 <div>
 作者：KesarChen 发表于2016/2/18 13:57:28 
 <a href="http://blog.csdn.net/kesarchen/article/details/50685624" rel="nofollow"> 原文链接</a> 
 </div> 
 <div>
 阅读：5266 评论：0 
 <a href="http://blog.csdn.net/kesarchen/article/details/50685624#comments" rel="nofollow"> 查看评论</a> 
 </div> </td> 
 </tr> 
 <tr> 
 <td>&nbsp;</td> 
 </tr> 
 <tr> 
 <td><a href="http://blog.csdn.net/kesarchen/article/details/50685621" rel="nofollow">[算法学习]复杂链表的复制</a></td> 
 </tr> 
 <tr> 
 <td> 
 <blockquote> 
 问题描述： 复制一个复杂链表。 在复杂链表中，每个结点除了有一个指向下一个结点的next指针外，还有一个 sibing指针 指向链表中任意结点或者NULL。 
 </blockquote> <h1>解法一：“爆破”</h1> 
 <blockquote> 
 解法分析： 1. 遍历第一遍数组，把复制链的next和各结点值复制好。需要时间O(n) 2. 第二遍遍历，二重for循环根据原链表，将复制链的slibing指针连接好。需要时间O(n^2) 3. 需要时间复杂度是O(n^2)，空间复杂度是O(1) 
 </blockquote> 
 <hr> <h2>参考代码如下</h2> <pre><code>/** * 复杂链表的结点 * * @author kesar * */
static class Node
{
 int val;
 Node next;
 Node slibing;

public Node(){}

public Node(int val)
 {
 this.val = val;
 }

@Override
 public String toString()
 {
 return "Node [val=" + val + "]";
 }
}

/** * 第一种解法：暴力复制。复制一遍next的，再每个结点遍历一遍进行slibing的比较。 时间复杂度是：O(n^2)，空间复杂度是：O(1) * * @param oHead * @return */
public static Node copy1(Node oHead)
{
 if (oHead == null)
 {
 return null;
 }
 // 复制的链表的头结点
 Node cHead = new Node(oHead.val);

// oMove是原链表上遍历用的移动指针，cMove是复制链表上遍历用的移动指针
 // 复制Node结点的值以及next链关系
 for (Node oMove = oHead.next, cMove = cHead; oMove != null; cMove = cMove.next, oMove = oMove.next)
 {
 cMove.next = new Node(oMove.val);
 }

// 复制slibing的链关系
 for (Node oMove = oHead, cMove = cHead; oMove != null; cMove = cMove.next, oMove = oMove.next)
 {
 if (oMove.slibing == null)
 continue;
 // 查找开始： 遍历查找slibing所指原链表结点对应在copy链表中的结点
 Node findNode = cHead;
 for (; findNode != null &amp;&amp; findNode.val != oMove.slibing.val; findNode = findNode.next)
 ;
 // 查找结束：findNode就是结果
 cMove.slibing = findNode;
 }

return cHead;
}</code></pre> <h1>解法二：使用辅助空间</h1> 
 <blockquote> 
 解法分析： 1. 使用一个HashMap(Key：原链表上的结点，Value：复制链表上的结点)，空间复杂度是O(n) 2. 遍历第一遍数组：每次创建复制链的结点时，需要先查找HashMap中结点是否存在，不存在才创建，然后保存结点到HashMap中。需要时间O(n) 4. 需要时间复杂度是O(n)，空间复杂度是O(n) 
 </blockquote> 
 <hr> <h2>参考代码如下</h2> <pre><code>/** * 第二种解法：利用HashMap的O(1)的高效率查找来取代第一中解法中的一个for循环。用O(n)的空间换来O(n)的时间。时间复杂度O(n)，空间复杂度：O(n) * * @param oHead * @return */
public static Node copy2(Node oHead)
{
 if (oHead == null)
 {
 return null;
 }
 // 辅助空间：Key：原链表上的结点，Value：复制链表上的结点
 HashMap&lt;Node, Node&gt; map = new HashMap&lt;Node, Node&gt;();

// 初始化复制链表的头结点
 Node cHead = new Node(oHead.val);
 map.put(oHead, cHead);
 if (oHead.slibing != null)
 {
 cHead.slibing = new Node(oHead.slibing.val);
 map.put(oHead.slibing, cHead.slibing);
 }
 // 作用：遍历原链表，复制结点到复制链表中。
 // 思路是这样：先从map找原结点对应的复制结点，如果没找到，就创建一个，然后连接到复制链表中，然后put入map中，便于其他时候使用
 for (Node oMove = oHead.next, cMove = cHead; oMove != null; oMove = oMove.next, cMove = cMove.next)
 {
 if (map.containsKey(oMove))
 {
 cMove.next = map.get(oMove);
 }
 else
 {
 cMove.next = new Node(oMove.val);
 map.put(oMove, cMove.next);
 }
 Node slibing = oMove.slibing;
 if (slibing == null)
 {
 continue;
 }
 if (map.containsKey(slibing))
 {
 cMove.next.slibing = map.get(slibing);
 }
 else
 {
 cMove.next.slibing = new Node(slibing.val);
 map.put(slibing, cMove.next.slibing);
 }
 }
 return cHead;
}</code></pre> <h1>解法三：“伸长分裂法”</h1> 
 <blockquote> 
 解法分析： 1. 遍历原链表。在原链表的每个结点的后面插入对应复制结点，将原链表“伸长”1倍； 2. 遍历原链表。将复制结点的slibing连接好； 3. 遍历原链表。将原结点和复制结点“分裂”开，将next连接好； 4. 需要时间复杂度是O(n)，空间复杂度是O(1) 
 </blockquote> 
 <hr> <h2>参考代码如下</h2> <pre><code>/** * @param oHead * @return */
public static Node copy3(Node oHead)
{
 if (oHead == null)
 {
 return null;
 }
 // 1."伸长"
 for (Node oMove = oHead; oMove != null; oMove = oMove.next)
 {
 // 复制结点
 Node copy = new Node(oMove.val);
 // 插入复制结点到原结点的后面
 copy.next = oMove.next;
 oMove.next = copy;
 // 移动到复制结点处
 oMove = copy;
 }
 // 2.连接好slibing
 for (Node oMove = oHead; oMove != null; oMove = oMove.next)
 {
 if (oMove.slibing == null)
 {
 continue;
 }
 Node copy = oMove.next;
 copy.slibing = oMove.slibing.next;
 oMove = copy;
 }
 // 3."分裂"，连接好原链表的next和复制链表中的next
 Node cHead = oHead.next;
 oHead.next = cHead.next;
 cHead.next = null;
 for (Node oMove = oHead.next, cMove = cHead; oMove != null; oMove = oMove.next, cMove = cMove.next)
 {
 Node copy = oMove.next;
 oMove.next = copy.next;
 copy.next = null;
 cMove.next = copy;
 }
 return cHead;
}</code></pre> 
 <ul> 
 <li>附：<a href="https://github.com/ClaymanTwinkle/SwordTest/blob/master/src/list/CopyComplexList.java" rel="nofollow">源码地址</a> </li> 
 </ul> 
 <div>
 作者：KesarChen 发表于2016/2/18 13:56:50 
 <a href="http://blog.csdn.net/kesarchen/article/details/50685621" rel="nofollow"> 原文链接</a> 
 </div> 
 <div>
 阅读：4892 评论：0 
 <a href="http://blog.csdn.net/kesarchen/article/details/50685621#comments" rel="nofollow"> 查看评论</a> 
 </div> </td> 
 </tr> 
 <tr> 
 <td>&nbsp;</td> 
 </tr> 
 <tr> 
 <td><a href="http://blog.csdn.net/kesarchen/article/details/50685613" rel="nofollow">[算法学习]求链表的中间结点</a></td> 
 </tr> 
 <tr> 
 <td> 
 <blockquote> 
 问题描述： 返回链表的中间结点（如果是两个则返回两个） 
 解法与分析： 用两个指针移动的方法来解决问题。一个指针每次移动1个结点，另外一个指针移动2个结点。 
 </blockquote> 
 <hr> <h2>参考代码如下</h2> <pre><code>static class ListNode
{
 int val;
 ListNode next;

public ListNode(int val)
 {
 this.val = val;
 }

public ListNode(int val, ListNode next)
 {
 this.val = val;
 this.next = next;
 }

@Override
 public String toString()
 {
 return "ListNode [val=" + val + "]";
 }
}

/** * 返回中间节点 * @param head * @return */
public static ListNode[] getCenterNode(ListNode head)
{
 ListNode[] results = { null, null };
 if (head == null)
 {
 return results;
 }
 ListNode left = head;
 ListNode right = head.next;
 // 如果只有一个节点
 if (right == null)
 {
 results[0] = left;
 return results;
 }
 // 如果不止有一个节点
 while (right.next != null)
 {
 left = left.next;
 right = right.next;
 right = right.next;
 if (right == null)
 {
 results[0] = left;
 return results;
 }
 }
 results[0] = left;
 results[1] = left.next;
 return results;
}</code></pre> 
 <ul> 
 <li>附：<a href="https://github.com/ClaymanTwinkle/SwordTest/blob/master/src/list/CenterNodeList.java" rel="nofollow">源码地址</a> </li> 
 </ul> 
 <div>
 作者：KesarChen 发表于2016/2/18 13:56:00 
 <a href="http://blog.csdn.net/kesarchen/article/details/50685613" rel="nofollow"> 原文链接</a> 
 </div> 
 <div>
 阅读：4397 评论：0 
 <a href="http://blog.csdn.net/kesarchen/article/details/50685613#comments" rel="nofollow"> 查看评论</a> 
 </div> </td> 
 </tr> 
 <tr> 
 <td>&nbsp;</td> 
 </tr> 
 <tr> 
 <td><a href="http://blog.csdn.net/kesarchen/article/details/50685606" rel="nofollow">[算法学习]求出链表中倒数第n个节点</a></td> 
 </tr> 
 <tr> 
 <td> 
 <blockquote> 
 问题描述： 求出链表中倒数第n个节点。例如：1,2,3,4,5，倒数第2个是4 
 解法与分析： 用两个指针的方法。 1. 第一个指针起始位置在0位置，第二个指针起始位置在n-1位置。 2. 两个指针同时移动，每次移动1个结点。 3. 当第二个指针移动到最后一个节点时，第一个指针所指结点就是倒数第n个结点。 
 </blockquote> 
 <hr> <h2>参考代码如下</h2> <pre><code>static class ListNode
{
 int val;
 ListNode next;

public ListNode(int val)
 {
 this.val = val;
 }

public ListNode(int val, ListNode next)
 {
 this.val = val;
 this.next = next;
 }

@Override
 public String toString()
 {
 return "ListNode [val=" + val + "]";
 }
}

public static ListNode getLastNode(ListNode head, int n)
{
 if (head == null || n &lt;= 0)
 {
 return null;
 }

ListNode left = head;
    ListNode right = head;

for (int i = 1; i &lt; n; i++)
 {
 right = right.next;
 if (right == null)
 {
 return null;
 }
 }
 while (right.next != null)
 {
 left = left.next;
 right = right.next;
 }
 return left;
}</code></pre> 
 <ul> 
 <li>附：<a href="https://github.com/ClaymanTwinkle/SwordTest/blob/master/src/list/LastList.java" rel="nofollow">源码地址</a> </li> 
 </ul> 
 <div>
 作者：KesarChen 发表于2016/2/18 13:55:19 
 <a href="http://blog.csdn.net/kesarchen/article/details/50685606" rel="nofollow"> 原文链接</a> 
 </div> 
 <div>
 阅读：5212 评论：0 
 <a href="http://blog.csdn.net/kesarchen/article/details/50685606#comments" rel="nofollow"> 查看评论</a> 
 </div> </td> 
 </tr> 
 <tr> 
 <td>&nbsp;</td> 
 </tr> 
 <tr> 
 <td><a href="http://blog.csdn.net/kesarchen/article/details/50685600" rel="nofollow">[算法学习]判断链表是否是环结构</a></td> 
 </tr> 
 <tr> 
 <td> 
 <blockquote> 
 问题描述： 判断链表是否是环结构。 
 解法与分析： 用两个指针的方法判断。 1. 第一个指针在第一个结点，第二个指针在第二个结点处； 2. 两个指针同时移动，第一个指针每次移动一个结点，第二个指针每次移动两个结点； 3. 当第二个指针和第一个指针指向的结点是同一个时，链表有环。 
 </blockquote> 
 <hr> <h2>参考代码如下</h2> <pre><code>static class ListNode
{
 int val;
 ListNode next;

public ListNode(int val)
 {
 this.val = val;
 }

public ListNode(int val, ListNode next)
 {
 this.val = val;
 this.next = next;
 }

@Override
 public String toString()
 {
 return "ListNode [val=" + val + "]";
 }
}

/** * 判断链表是否是环结构 * @param head * @return */
public static boolean isLoop(ListNode head)
{
 if(head==null||head.next==null)
 {
 return false;
 }
 ListNode pSlow=head;
 ListNode pFast=head.next;

while (pFast.next!=null)
 {
 if(pFast.equals(pSlow))
 {
 return true;
 }
 pSlow=pSlow.next;
 pFast=pFast.next;
 pFast=pFast.next;
 if(pFast==null)
 {
 return false;
 }
 }
 return false;
}</code></pre> 
 <ul> 
 <li>附：<a href="https://github.com/ClaymanTwinkle/SwordTest/blob/master/src/list/LoopList.java" rel="nofollow">源码地址</a> </li> 
 </ul> 
 <div>
 作者：KesarChen 发表于2016/2/18 13:54:34 
 <a href="http://blog.csdn.net/kesarchen/article/details/50685600" rel="nofollow"> 原文链接</a> 
 </div> 
 <div>
 阅读：5303 评论：0 
 <a href="http://blog.csdn.net/kesarchen/article/details/50685600#comments" rel="nofollow"> 查看评论</a> 
 </div> </td> 
 </tr> 
 <tr> 
 <td>&nbsp;</td> 
 </tr> 
 <tr> 
 <td><a href="http://blog.csdn.net/kesarchen/article/details/50685597" rel="nofollow">[算法学习]合并两个排序的链表</a></td> 
 </tr> 
 <tr> 
 <td> 
 <blockquote> 
 问题描述： 合并两个排序的链表。 
 </blockquote> <h1>解法一：用递归</h1> 
 <blockquote> 
 解法： 递归比较结点大小：每次递归，取出两个链表的头结点来比较，比较小的结点加入新链表中。 
 </blockquote> 
 <hr> <h2>参考代码如下</h2> <pre><code>/** * 用递归 * @param head1 * @param head2 * @return */
public static ListNode merge(ListNode head1, ListNode head2)
{
 if(head1==null)
 {
 return head2;
 }
 if(head2==null)
 {
 return head1;
 }
 ListNode head;
 if(head1.value&lt;head2.value)
 {
 head=head1;
 head.next=merge(head1.next, head2);
 }
 else
 {
 head=head2;
 head.next=merge(head1, head2.next);
 }
 return head;
}</code></pre> <h1>解法二：用循环</h1> 
 <blockquote> 
 解法： 使用指针移动的方式来遍历两个链表。每次两个指针停止，进行结点比较，较小的结点加到新链表中。 
 </blockquote> 
 <hr> <h2>参考代码如下</h2> <pre><code>/** * 用循环 * @param head1 * @param head2 * @return */
public static ListNode merge1(ListNode head1, ListNode head2)
{
 if (head1 == null)
 {
 return head2;
 }
 if (head2 == null)
 {
 return head1;
 }
 ListNode head;
 if (head1.value &lt; head2.value)
 {
 head = head1;
 head1 = head1.next;
 }
 else
 {
 head = head2;
 head2 = head2.next;
 }
 ListNode move = head;
 while (head1 != null || head2 != null)
 {
 if (head1 == null)
 {
 move.next = head2;
 head2 = head2.next;
 }
 else if (head2 == null)
 {
 move.next = head1;
 head1 = head1.next;
 }
 else if (head1.value &lt; head2.value)
 {
 move.next = head1;
 head1 = head1.next;
 }
 else
 {
 move.next = head2;
 head2 = head2.next;
 }
 if(move.value&gt;move.next.value)
 {
 System.err.println("输入的链表不是有序的");
 return null;
 }
 move = move.next;
 }
 return head;
}</code></pre> 
 <ul> 
 <li>附：<a href="https://github.com/ClaymanTwinkle/SwordTest/blob/master/src/list/MergeList.java" rel="nofollow">源码地址</a> </li> 
 </ul> 
 <div>
 作者：KesarChen 发表于2016/2/18 13:53:35 
 <a href="http://blog.csdn.net/kesarchen/article/details/50685597" rel="nofollow"> 原文链接</a> 
 </div> 
 <div>
 阅读：5001 评论：0 
 <a href="http://blog.csdn.net/kesarchen/article/details/50685597#comments" rel="nofollow"> 查看评论</a> 
 </div> </td> 
 </tr> 
 <tr> 
 <td>&nbsp;</td> 
 </tr> 
 <tr> 
 <td><a href="http://blog.csdn.net/kesarchen/article/details/50685594" rel="nofollow">[算法学习]反转链表</a></td> 
 </tr> 
 <tr> 
 <td> 
 <blockquote> 
 问题描述： 输入一条链表，将链表反转后返回。 
 </blockquote> <h1>解法一：用递归</h1> 
 <blockquote> 
 解法： 由于反转后头结点会成为尾结点，尾结点会成会头结点。所以从头结点开始反转前后结点关系。比较简单，所以这里直接贴出代码。 
 </blockquote> 
 <hr> <h2>参考代码如下</h2> <pre><code>/** * 递归 * @param head * @return */
public static ListNode reverseList1(ListNode head)
{
 if(head==null)
 {
 return null;
 }
 ListNode parent=head.next;
 if(parent==null)
 {
 return head;
 }
 head.next=null;
 return reverseList1(head,parent);
}

/** * 递归，绑定父子节点关系 * @param child * @param parent * @return */
private static ListNode reverseList1(ListNode child,ListNode parent)
{
 if(parent==null)
 {
 return child;
 }
 ListNode last=parent.next;
 parent.next=child;
 return reverseList1(parent, last);
}</code></pre> <h1>解法二：用循环，效率更高</h1> 
 <hr> <h2>参考代码如下</h2> <pre><code>/** * 反转链表，返回新的头节点 * @param head * @return */
public static ListNode reverseList(ListNode head)
{
 if(head==null)
 {
 return null;
 }
 ListNode pChild=head;
 ListNode pParent=pChild.next;
 ListNode pLast=null;
 pChild.next=null;
 while (pParent!=null)
 {
 // 绑定关系
 pLast=pParent.next;
 pParent.next=pChild;
 // 设定关系
 pChild=pParent;
 pParent=pLast;
 }
 return pChild;
}</code></pre> 
 <ul> 
 <li>附：<a href="https://github.com/ClaymanTwinkle/SwordTest/blob/master/src/list/ReverseList.java" rel="nofollow">源码地址</a> </li> 
 </ul> 
 <div>
 作者：KesarChen 发表于2016/2/18 13:52:54 
 <a href="http://blog.csdn.net/kesarchen/article/details/50685594" rel="nofollow"> 原文链接</a> 
 </div> 
 <div>
 阅读：5088 评论：0 
 <a href="http://blog.csdn.net/kesarchen/article/details/50685594#comments" rel="nofollow"> 查看评论</a> 
 </div> </td> 
 </tr> 
 <tr> 
 <td>&nbsp;</td> 
 </tr> 
 <tr> 
 <td><a href="http://blog.csdn.net/kesarchen/article/details/50685587" rel="nofollow">[算法学习]计算出二进制数中1的个数</a></td> 
 </tr> 
 <tr> 
 <td> 
 <blockquote> 
 问题描述： 计算出二进制数中1的个数。 
 </blockquote> <h1>解法一：循环计数</h1> 
 <blockquote> 
 解法与分析： 使用一个数1来“与”二进制数中每一位，若值为1则1的个数加一。 
 </blockquote> 
 <hr> <h2>参考代码如下</h2> <pre><code>/** * 通过flag左移做一个循环来与num的每一位，若与计算的结果不为0，则1的个数++ * @param num * @return */
public static int calc2(int num)
{
 int count=0;
 int flag=1;
 while (flag!=0)
 {
 if((num&amp;flag)!=0)
 {
 count++;
 }
 flag&lt;&lt;=1;
 }

return count;
}</code></pre> <h1>解法二：最佳算法</h1> 
 <blockquote> 
 解法与分析： 设二进制数为num，若num不为0时，num-1后的值与num相与都会消除一个1，按照这一点，可以很快计算出1个个数。 
 </blockquote> 
 <hr> <h2>参考代码如下</h2> <pre><code>/** * num不为0时，num-1后的值与num相与都会消除一个1，按照这一点，可以很快计算出1个个数，最佳算法 * @param num * @return */
public static int calc3(int num)
{
 int count=0;
 while (num!=0)
 {
 num=num&amp;(num-1);
 count++;
 }
 return count;
}</code></pre> 
 <ul> 
 <li>附：<a href="https://github.com/ClaymanTwinkle/SwordTest/blob/master/src/num/NumberOf1InBinary.java" rel="nofollow">源码地址</a> </li> 
 </ul> 
 <div>
 作者：KesarChen 发表于2016/2/18 13:52:00 
 <a href="http://blog.csdn.net/kesarchen/article/details/50685587" rel="nofollow"> 原文链接</a> 
 </div> 
 <div>
 阅读：5165 评论：0 
 <a href="http://blog.csdn.net/kesarchen/article/details/50685587#comments" rel="nofollow"> 查看评论</a> 
 </div> </td> 
 </tr> 
 <tr> 
 <td>&nbsp;</td> 
 </tr> 
 <tr> 
 <td><a href="http://blog.csdn.net/kesarchen/article/details/50685581" rel="nofollow">[算法学习]栈中的最小值</a></td> 
 </tr> 
 <tr> 
 <td> 
 <blockquote> 
 问题描述： 实现栈的pop、push、 min (得到栈中最小值)方法。 
 解法与分析： 1. 由于每次压栈和出栈都可能会改变栈中的最小值，所以，我们增加一个存放最小值的栈。 2. 当出栈操作时，最小值的栈也出栈；(当然，必须判断栈是否为空) 3. 当压栈操作时，比较压栈元素值和最小栈的栈顶元素的大小，若比较小，则将它压入栈中，若不是，则将最小栈的栈顶元素重复压栈。(当然，必须判断栈是否为空) 
 </blockquote> 
 <hr> <h2>参考代码如下</h2> <pre><code> private Stack&lt;Integer&gt; dataStack = new Stack&lt;Integer&gt;();
 private Stack&lt;Integer&gt; minStack = new Stack&lt;Integer&gt;();

/** * 出栈 * @return */
 public int pop()
 {
 if (minStack.isEmpty() &amp;&amp; dataStack.isEmpty())
 {
 throw new EmptyStackException();
 }
 minStack.pop();
 return dataStack.pop();
 }

/** * 压栈 * @param item */
 public void push(int item)
 {
 dataStack.push(item);
 if(minStack.isEmpty()||item&lt;minStack.peek())
 {
 minStack.push(item);
 }
 else
 {
 minStack.push(minStack.peek());
 }
 }

/** * 取最小值 * @return */
 public int min()
 {
 if(minStack.isEmpty())
 {
 throw new EmptyStackException();
 }
 return minStack.peek();
 }</code></pre> 
 <ul> 
 <li>附：<a href="https://github.com/ClaymanTwinkle/SwordTest/blob/master/src/stackandqueue/MinStack.java" rel="nofollow">源码地址</a> </li> 
 </ul> 
 <div>
 作者：KesarChen 发表于2016/2/18 13:51:19 
 <a href="http://blog.csdn.net/kesarchen/article/details/50685581" rel="nofollow"> 原文链接</a> 
 </div> 
 <div>
 阅读：4910 评论：0 
 <a href="http://blog.csdn.net/kesarchen/article/details/50685581#comments" rel="nofollow"> 查看评论</a> 
 </div> </td> 
 </tr> 
 <tr> 
 <td>&nbsp;</td> 
 </tr> 
 <tr> 
 <td><a href="http://blog.csdn.net/kesarchen/article/details/50685577" rel="nofollow">[算法学习]栈的出栈序列</a></td> 
 </tr> 
 <tr> 
 <td> 
 <blockquote> 
 问题描述： 输入数字不重复的两组整数序列：压栈的序列A,出栈的序列B，验证AB是否为同一栈的序列。 
 解法与分析： 1. 使用两个指针pA，pB分别在两个序列A，B上遍历。 2. 做个这样的判断，首先判断两个指针所指元素是否相等，若相等，则两个指针同时推进；若不相等，取出栈顶元素作比较；若与栈顶元素不相等，则序列A的元素入栈，pA指针向前推进，若与栈顶元素相等，则出栈，pB指针推进。 
 </blockquote> 
 <hr> <h2>参考代码如下</h2> <pre><code>public static boolean isStackSeq(int[] pushSeq, int[] popSeq)
{
 if (popSeq == null || pushSeq == null
 || pushSeq.length != popSeq.length)
 {
 return false;
 }
 Stack&lt;Integer&gt; stack = new Stack&lt;Integer&gt;();
 int pushIndex = 0;
 int popIndex = 0;

while (popIndex &lt; popSeq.length)
 {
 if (pushIndex &lt; pushSeq.length)
 {
 if (pushSeq[pushIndex] == popSeq[popIndex])
 {
 pushIndex++;
 popIndex++;
 continue;
 }
 if (!stack.isEmpty() &amp;&amp; stack.peek() == popSeq[popIndex])
 {
 stack.pop();
 popIndex++;
 }
 else
 {
 stack.push(pushSeq[pushIndex++]);
 }
 }
 else if (!stack.isEmpty() &amp;&amp; stack.pop() == popSeq[popIndex])
 {
 popIndex++;
 }
 else
 {
 return false;
 }
 }
 return stack.isEmpty();
}</code></pre> 
 <ul> 
 <li>附：<a href="https://github.com/ClaymanTwinkle/SwordTest/blob/master/src/stackandqueue/StackSequence.java" rel="nofollow">源码地址</a> </li> 
 </ul> 
 <div>
 作者：KesarChen 发表于2016/2/18 13:50:39 
 <a href="http://blog.csdn.net/kesarchen/article/details/50685577" rel="nofollow"> 原文链接</a> 
 </div> 
 <div>
 阅读：5281 评论：0 
 <a href="http://blog.csdn.net/kesarchen/article/details/50685577#comments" rel="nofollow"> 查看评论</a> 
 </div> </td> 
 </tr> 
 <tr> 
 <td>&nbsp;</td> 
 </tr> 
 <tr> 
 <td><a href="http://blog.csdn.net/kesarchen/article/details/50685567" rel="nofollow">[算法学习]二叉搜索树转双向链表</a></td> 
 </tr> 
 <tr> 
 <td> 
 <blockquote> 
 问题描述： 将一棵二叉搜索树转成一条排序好的双向链表。要求不能创建新结点。 
 解法与分析： 1. 由于左子树&lt;根结点&lt;右子树，所以双向链表的头结点是二叉搜索树左子树中的最后一个左结点，双向链表的头结点是二叉搜索树右子树中的最后一个右结点，根结点则是链表的中间结点。 2. 将树结点中指向左孩子的指针作为双向链表中的前驱指针，指向右孩子的指针作为双向链表指向后继结点的指针。 3. 按照上面分析，可以使用树的中序遍历来转换双向链表。这里我们使用递归的方式来实现中序遍历+双向链表转换。 
 </blockquote> 
 <hr> <h2>参考代码如下</h2> <pre><code>/** * 树节点 */
static class TreeNode
{
 int val;
 TreeNode left;
 TreeNode right;

public TreeNode(int val)
 {
 this.val = val;
 }

public TreeNode(int val, TreeNode left, TreeNode right)
 {
 this.val = val;
 this.left = left;
 this.right = right;
 }
}
/** * 解法：中序遍历的顺序，中间增加连接节点的操作。 * @param root * @return */
public static TreeNode doBST2BWL(TreeNode root)
{
 if(root==null)
 {
 return null;
 }
 TreeNode head=root;
 // 整理左半边
 TreeNode left = doBST2BWL(root.left);
 // 连接左半边
 if(left!=null)
 {
 head=left;
 // 将left指针移动到左半边的最后(右)一个结点
 for(;left.right!=null;left=left.right);
 left.right=root;
 }
 root.left=left;
 // 整理右半边
 TreeNode right= doBST2BWL(root.right);
 // 连接右半边
 if(right!=null)
 {
 right.left=root;
 }
 root.right=right;
 // 返回头结点
 return head;
}</code></pre> 
 <ul> 
 <li>附：<a href="https://github.com/ClaymanTwinkle/SwordTest/blob/master/src/tree/BST2BWL.java" rel="nofollow">源码地址</a> </li> 
 </ul> 
 <div>
 作者：KesarChen 发表于2016/2/18 13:49:50 
 <a href="http://blog.csdn.net/kesarchen/article/details/50685567" rel="nofollow"> 原文链接</a> 
 </div> 
 <div>
 阅读：5038 评论：0 
 <a href="http://blog.csdn.net/kesarchen/article/details/50685567#comments" rel="nofollow"> 查看评论</a> 
 </div> </td> 
 </tr> 
 <tr> 
 <td>&nbsp;</td> 
 </tr> 
 <tr> 
 <td><a href="http://blog.csdn.net/kesarchen/article/details/50685556" rel="nofollow">[算法学习]打印树的路径</a></td> 
 </tr> 
 <tr> 
 <td> 
 <blockquote> 
 问题描述： 输入一个整数sum和一棵二叉树，打印出二叉树中结点和为sum的所有路径。 （路径：从根结点往下一直到叶结点形成的一条路径。） 
 解法与分析： 1. 需要从树上的根结点遍历到叶子结点，其中需要累加经过结点的值。 2. 当累加到叶子结点时，比较累加结点值和sum的值，如果相等，打印出路径；如果不相等，返回到上一层，寻找其他叶子结点。 3. 需要保存结点路径，还可以返回到上一个结点，可以选择用栈来保存经过结点。 4. 可以使用递归来描述这个解法。 
 </blockquote> 
 <hr> <h2>参考代码如下</h2> <pre><code>/** * 树结点 */
static class TreeNode
{
 int val;
 TreeNode left;
 TreeNode right;

public TreeNode(int val)
 {
 this.val = val;
 }

/** * 寻找路径 */
public static void findPath(TreeNode root, int sum)
{
 if (root == null) return;
 Stack&lt;Integer&gt; paths = new Stack&lt;Integer&gt;();
 findPath(root, paths, sum, 0);
}

/** * 递归寻找路径 */
private static void findPath(TreeNode root, Stack&lt;Integer&gt; paths, int sum,int currentSum)
{
 currentSum += root.val;
 boolean isLeaf = root.left == null &amp;&amp; root.right == null;
 paths.push(root.val);
 if (isLeaf &amp;&amp; currentSum == sum)
 {
 printPath(paths);
 }
 if (root.left != null)
 {
 findPath(root.left, paths, sum, currentSum);
 }
 if (root.right != null)
 {
 findPath(root.right, paths, sum, currentSum);
 }
 paths.pop();
}

/** * 打印路径 */
static void printPath(Stack&lt;Integer&gt; paths)
{
 if (paths.isEmpty()) return;
 for (Integer item : paths)
 {
 System.out.print(item + " - ");
 }
 System.out.println();
}</code></pre> 
 <ul> 
 <li>附：<a href="https://github.com/ClaymanTwinkle/SwordTest/blob/master/src/tree/FindPathByNodeValue.java" rel="nofollow">源码地址</a> </li> 
 </ul> 
 <div>
 作者：KesarChen 发表于2016/2/18 13:48:59 
 <a href="http://blog.csdn.net/kesarchen/article/details/50685556" rel="nofollow"> 原文链接</a> 
 </div> 
 <div>
 阅读：5086 评论：0 
 <a href="http://blog.csdn.net/kesarchen/article/details/50685556#comments" rel="nofollow"> 查看评论</a> 
 </div> </td> 
 </tr> 
 <tr> 
 <td>&nbsp;</td> 
 </tr> 
 <tr> 
 <td><a href="http://blog.csdn.net/kesarchen/article/details/50685546" rel="nofollow">[算法学习]树的子结构</a></td> 
 </tr> 
 <tr> 
 <td> 
 <blockquote> 
 问题描述： 判断树A是否是树B的子结构。 
 解法与分析： 使用递归的方式很容易解决。先进行根结点比较，相等的话，递归左右子树。 
 </blockquote> 
 <hr> <h2>参考代码如下</h2> <pre><code>public static boolean isIncludeTree(TreeNode parent, TreeNode child)
{
 boolean result = false;
 if (parent == null || child == null)
 {
 return result;
 }
 if (parent.value==child.value)
 {
 result = hasTree(parent, child);
 }
 if (!result)
 {
 result = isIncludeTree(parent.left, child);
 }
 if (!result)
 {
 result = isIncludeTree(parent.right, child);
 }

return result;
}

private static boolean hasTree(TreeNode parent, TreeNode child)
{
 if (child == null)
 {
 return true;
 }
 if (parent == null||parent.value!=child.value)
 {
 return false;
 }

return hasTree(parent.left, child.left) &amp;&amp; hasTree(parent.right, child.right);
}
</code></pre> 
 <ul> 
 <li>附：<a href="https://github.com/ClaymanTwinkle/SwordTest/blob/master/src/tree/IncludeSonTree.java" rel="nofollow">源码地址</a> </li> 
 </ul> 
 <div>
 作者：KesarChen 发表于2016/2/18 13:47:26 
 <a href="http://blog.csdn.net/kesarchen/article/details/50685546" rel="nofollow"> 原文链接</a> 
 </div> 
 <div>
 阅读：5014 评论：0 
 <a href="http://blog.csdn.net/kesarchen/article/details/50685546#comments" rel="nofollow"> 查看评论</a> 
 </div> </td> 
 </tr> 
 <tr> 
 <td>&nbsp;</td> 
 </tr> 
 <tr> 
 <td><a href="http://blog.csdn.net/kesarchen/article/details/50685534" rel="nofollow">[算法学习]树的镜像</a></td> 
 </tr> 
 <tr> 
 <td> 
 <blockquote> 
 问题描述： 输出树的镜像。 
 解法与分析： 根结点不变，左右子树交换。按照这一点进行递归，就可以解决问题。 
 </blockquote> 
 <hr> <h2>参考代码如下</h2> <pre><code>public static TreeNode mirror(TreeNode root)
{
 if(root==null) return null;

TreeNode left=root.left;
 TreeNode right=root.right;
 root.right=mirror(left);
 root.left=mirror(right);
 return root;
}</code></pre> 
 <ul> 
 <li>附：<a href="https://github.com/ClaymanTwinkle/SwordTest/blob/master/src/tree/MirroringTree.java" rel="nofollow">源码地址</a> </li> 
 </ul> 
 <div>
 作者：KesarChen 发表于2016/2/18 13:46:15 
 <a href="http://blog.csdn.net/kesarchen/article/details/50685534" rel="nofollow"> 原文链接</a> 
 </div> 
 <div>
 阅读：5145 评论：0 
 <a href="http://blog.csdn.net/kesarchen/article/details/50685534#comments" rel="nofollow"> 查看评论</a> 
 </div> </td> 
 </tr> 
 </tbody> 
</table>