随机取样的实现

程序的输入包含两个整数m和n,其中 m <n 。输出是 0~n-1 范围内 m 个随机整数的有序列表,不允许重复。
从概率的角度说,我们希望得到没有重复的有序选择,其中每个选择出现的概率相等。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Random;

public class RandomSample {

    /**
     * 随机取样
     *
     * @param bound 样本总数
     * @param count 需要抽取的样本数
     * @return 返回一个有序数组
     */
    public static int[] getRandomSamples(int bound, int count) {
        if (count < 1 || bound <= count) {
            return null;
        }

        boolean[] fillArray = new boolean[bound];
        for (int i = 0; i < bound; i++) {
            fillArray[i] = false; //用false标示未填充,true表示已填充。
        }

        Random random = new Random();
        int fillCount = 0;
        final int randomNumCount = Math.min(count, bound - count); //随机填充的数目不超过一半
        while (fillCount < randomNumCount) {
            int num = random.nextInt(bound);
            if (!fillArray[num]) {
                fillArray[num] = true;
                fillCount++;
            }
        }

        int[] samples = new int[count];
        //如果随机抽取的数量与所需相等,则取该集合;否则取补集。
        int index = 0;
        if (randomNumCount == count) {
            for (int i = 0; i < bound; i++) {
                if (fillArray[i]) {
                    samples[index++] = i;
                }
            }
        } else {
            //取补集
            for (int i = 0; i < bound; i++) {
                if (!fillArray[i]) {
                    samples[index++] = i;
                }
            }
        }
        return samples;
    }

    /**
     * 通过洗牌的方式随机取样
     */
    public static int[] getRandomSamples2(int bound, int count) {
        if (count < 1 || bound <= count) {
            return null;
        }
        List<Integer> list = new ArrayList<>(bound);
        for (int i = 0; i < bound; i++) {
            list.add(i);
        }
        Collections.shuffle(list);
        int[] samples = new int[count];
        for (int i = 0; i < count; i++) {
            samples[i] = list.get(i);
        }
        return samples;
    }

    public static void main(String[] args) {
        int[] r1 = getRandomSamples(100, 10);
        int[] r2 = getRandomSamples2(200, 10);
        System.out.println(Arrays.toString(r1));
        System.out.println(Arrays.toString(r2));
    }

}

作者:DreamWinter
链接:https://www.jianshu.com/p/32902050f7dd
来源:简书
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

最短路径算法

import java.util.PriorityQueue;

public class Dijkstra {

	/**
	 * 1.假设带权有向图G的顶点集合为V,起始点为V0。
	 * 2.初始S={V0},T=V-S={其余顶点},其中集合S表示已经计算出最短距离的顶点,T是还没计算的剩余顶点。
	 * 3.初始化V0到其余各点的距离,D(V0,Vi)代表V0到Vi的最短距离,按如下规则。
	 * 3.若V0可以直接到达某个顶点Vi,则将边的权值赋给(V0,Vi),否则D(V0,Vi)=∞。
	 * 5.从T中选取一个与S中顶点有关联(直接相连)且权值最小的顶点W(这里用到了贪心法思想),加入到S中。
	 * 6.以W作为中间点,若V0到T中某个顶点Vi距离变短,则修改D(V0,Vi)的值。 
	 * 7.重复5)和6)直到T为空。
	 * 
	 * @param src
	 * @param dst
	 * @param graph
	 * @param n
	 * @return
	 */
	public static int dijkstra(int src, int dst, int[][] graph, int n) {
		// 排序队列
		PriorityQueue<Node> pNodes = new PriorityQueue<>();
		int[] visitLog = new int[n + 1];
		// 记录访问过的点
		pNodes.add(new Node(src, 0));
		while (!pNodes.isEmpty()) {
			Node tNode = pNodes.poll();
			// 由于已经排序了 直接返回的就是最短路径
			if (tNode.node == dst) {
				return tNode.cost;
			}
			if (visitLog[tNode.node] == 1) {
				continue;
			}
			visitLog[tNode.node] = 1;
			for (int i = 0; i < n; i++) {
				// 可联通且没有遍历过
				if (graph[tNode.node][i] < 1000 && visitLog[i] != 1) {
					pNodes.add(new Node(i, tNode.cost + graph[tNode.node][i]));
				}
			}
		}
		return -1;
	}

	public static void main(String[] args) {
		int graph[][] = { { 0, 2, 3, 6, 1000, 1000 }, { 2, 0, 1000, 1000, 4, 6 }, { 3, 1000, 0, 2, 1000, 1000 },
				{ 6, 1000, 2, 0, 1, 3 }, { 1000, 4, 1000, 1, 0, 1000 }, { 1000, 6, 1000, 3, 1000, 0 } };// 地图

		System.out.println(Dijkstra.dijkstra(0, 3, graph, 6));
		System.out.println(Floyd.floyd(0, 3, graph, 6));
	}
}

/**
 * 
 * @author shichaopeng
 *
 *
 *
 *         邻接矩阵graph储存路径,同时最终状态代表点点的最短路径。如果没有直接相连的两点那么默认为一个很大的值(不要溢出)!而自己的长度为0.
 *         从第1个到第n个点依次加入图中。每个点加入进行试探是否有路径长度被更改。
 *         而上述试探具体方法为遍历图中每一个点(i,j双重循环),判断每一个点对距离是否因为加入的点而发生最小距离变化。如果发生改变,那么两点(i,j)距离就更改。
 *         重复上述直到最后插点试探完成。
 * 
 *         状态转移方程为: dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])
 *         其中dp[x][y]的意思可以理解为x到y的最短路径。所以dp[i][k]的意思可以理解为i到k的最短路径dp[k][j]的意思可以理解为k到j的最短路径.
 */
class Floyd {

	/**
	 * 
	 * @param src
	 * @param dst
	 * @param graph
	 * @param n
	 * @return
	 */
	public static int floyd(int src, int dst, int[][] graph, int n) {
		int[][] r = new int[n][n];
		for (int i = 0; i < r.length; i++) {
			for (int j = 0; j < r.length; j++) {
				r[i][j] = graph[i][j];
			}
		}
		for (int k = 0; k < n; k++) { // 任意2点插入点 让后动态规划
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					r[i][j] = Math.min(r[i][j], graph[i][k] + graph[k][j]);
				}
			}
		}
		return r[src][dst];
	}

}

class Node implements Comparable<Node> {

	public int node;
	public int cost;

	public Node(int node, int cost) {
		super();
		this.node = node;
		this.cost = cost;
	}

	@Override
	public int compareTo(Node o) {
		return cost - o.cost;
	}

}

洗牌算法

-- To shuffle an array a of n elements (indices 0..n-1):
for i from n−1 downto 1 do
     j ← random integer such that 0 ≤ j ≤ i
     exchange a[j] and a[i]

java 实现

import java.util.Arrays;
import java.util.Random;

public class Shuffle {

	public static void shuffle(int[] arr) {
		int i = arr.length;
		Random random = new Random();
		while (i > 1) {
			i = i - 1;
			int j = random.nextInt(i);
			int temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;
		}
		System.out.println(Arrays.toString(arr));
	}

	public static void main(String[] args) {
		int[] arr = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
		for (int i = 0; i < 50; i++)
			shuffle(arr);
	}
}

运行50次结果

[7, 3, 0, 2, 9, 1, 8, 4, 6, 5]
[3, 2, 5, 9, 1, 6, 7, 0, 4, 8]
[7, 8, 6, 1, 4, 2, 0, 9, 5, 3]
[9, 3, 1, 7, 5, 6, 4, 8, 2, 0]
[5, 9, 0, 2, 1, 4, 7, 6, 3, 8]
[4, 8, 3, 9, 6, 1, 5, 0, 2, 7]
[0, 6, 9, 1, 3, 5, 4, 2, 7, 8]
[6, 3, 8, 4, 5, 2, 0, 9, 1, 7]
[8, 9, 3, 1, 4, 7, 6, 2, 0, 5]
[1, 8, 4, 7, 2, 3, 0, 5, 9, 6]
[9, 1, 3, 5, 0, 8, 6, 4, 2, 7]
[1, 7, 9, 4, 6, 3, 8, 0, 5, 2]
[0, 8, 4, 7, 3, 2, 6, 5, 9, 1]
[1, 7, 8, 9, 6, 5, 0, 4, 3, 2]
[5, 4, 1, 8, 0, 7, 3, 2, 9, 6]
[8, 6, 2, 0, 1, 5, 9, 3, 4, 7]
[5, 7, 4, 9, 0, 3, 6, 2, 1, 8]
[8, 9, 5, 4, 7, 0, 1, 3, 2, 6]
[2, 5, 6, 7, 3, 1, 4, 9, 0, 8]
[0, 7, 8, 2, 6, 5, 9, 1, 3, 4]
[4, 3, 6, 0, 5, 1, 2, 9, 8, 7]
[6, 1, 5, 8, 9, 4, 7, 0, 2, 3]
[9, 4, 0, 2, 5, 6, 3, 8, 7, 1]
[5, 2, 7, 0, 4, 3, 9, 6, 1, 8]
[4, 3, 1, 7, 9, 0, 6, 2, 8, 5]
[5, 8, 6, 1, 4, 9, 2, 0, 7, 3]
[3, 0, 2, 6, 1, 5, 8, 7, 9, 4]
[1, 6, 0, 4, 7, 3, 5, 9, 2, 8]
[5, 8, 6, 0, 2, 4, 7, 3, 9, 1]
[8, 7, 3, 6, 4, 1, 0, 9, 2, 5]
[9, 0, 7, 1, 5, 8, 4, 3, 6, 2]
[0, 4, 9, 7, 8, 1, 6, 5, 2, 3]
[5, 0, 4, 2, 1, 7, 9, 8, 3, 6]
[7, 2, 8, 3, 5, 4, 1, 0, 6, 9]
[2, 6, 4, 8, 0, 5, 9, 7, 1, 3]
[0, 2, 9, 7, 8, 6, 1, 4, 3, 5]
[6, 4, 1, 2, 9, 7, 5, 3, 8, 0]
[3, 2, 4, 0, 5, 9, 8, 1, 6, 7]
[9, 0, 8, 7, 6, 2, 3, 4, 1, 5]
[4, 1, 5, 3, 8, 9, 0, 6, 2, 7]
[8, 5, 6, 0, 2, 4, 7, 3, 1, 9]
[1, 4, 9, 6, 3, 2, 8, 7, 0, 5]
[9, 5, 6, 2, 0, 7, 1, 3, 4, 8]
[1, 8, 3, 6, 4, 5, 7, 0, 9, 2]
[8, 3, 7, 5, 1, 9, 0, 2, 4, 6]
[2, 0, 6, 4, 5, 1, 9, 7, 8, 3]
[9, 6, 1, 2, 4, 8, 3, 5, 7, 0]
[6, 3, 4, 0, 2, 1, 8, 9, 5, 7]
[2, 9, 1, 3, 5, 6, 4, 8, 7, 0]
[3, 5, 7, 1, 6, 0, 8, 9, 4, 2]

打印杨辉三角

构造杨辉三角逻辑并不难,主要打印格式的对齐比较困难.

public class Main {

	/**
	 * 计算行应该占得宽度
	 * 每个数字额外加了一个空格,数字的宽度加空格的宽度
	 * @param lastIntegers
	 * @return
	 */
	static int width_of(int[] lastIntegers) {
		int width = 0;
		int length = 0;
		for (int lastInteger : lastIntegers) {
			if (lastInteger > 0) {
				width += numWidth(lastInteger);
				length++;
			}
		}
		width += length;
		return width;
	}

	static int numWidth(int num) {
		int count = 0;
		while (num > 0) {
			num = num / 10;
			count++;
		}
		return count;
	}

	public static void main(String[] args) {
		int n = 10;
		int[][] result = new int[n][n];
		result[0][0] = 1;
		result[1][0] = 1;
		result[1][1] = 1;
		//构造杨辉三角
		for (int i = 2; i < n; i++) {
			result[i][0] = 1;
			result[i][i] = 1;
			for (int j = 1; j <= i - 1; j++) {
				result[i][j] = result[i - 1][j - 1] + result[i - 1][j];
			}
		}
		int maxWidth = width_of(result[n - 1]);
		for (int i = 0; i < n; i++) {
			int[] temp = result[i];
			int temp_width = width_of(temp);
			int wihteBlankLength = (maxWidth - temp_width) / 2;
			for (int k = 0; k < wihteBlankLength; k++) {
				System.out.print(" ");
			}
			for (int j = 0; j < temp.length; j++) {
				if (temp[j] > 0)
					System.out.print(String.format("%d", temp[j]) + " ");
			}
			System.out.println();
		}
	}

}

斐波那契数列


import java.util.HashMap;
import java.util.Map;

public class Fibonacci {

	// F(0)=0, F(1)=1, n>1时,F(n)=F(n-1)+F(n-2)。
	public static int fibonacci(int n) {
		if (n == 0 || n == 1) {
			return n;
		}
		return fibonacci(n - 1) + fibonacci(n - 2);
	}

	/**
	 * 缓存执行结果
	 */
	static Map<Integer, Integer> cacheList = new HashMap<>();
	static {
		cacheList.put(0, 0);
		cacheList.put(1, 1);
	}

	public static int fibonacciUseCache(int n) {
		int r = cacheList.containsKey(n) ? cacheList.get(n) : 0;
		if (r == 0) {
			r = fibonacci(n - 1) + fibonacci(n - 2);
		}
		cacheList.put(n, r);
		return r;
	}

	/**
	 * 动态规划:从底部开始解决问题,将所有小问题解决掉,然后合并成一个整体解决方案,从而解决掉整个大问题;
	 * 递归:从顶部开始将问题分解,通过解决掉所有分解的小问题来解决整个问题;
	 * 
	 * @param n
	 * @return
	 */
	public static int fibonacciDynamic(int n) {
		int current = 0;
		int next = 1;
		int temp;
		for (int i = 0; i < n; i++) {
			temp = current;
			current = next;
			next += temp;
		}
		return current;
	}

	public static int fibonacciDynamic2(int n) {
		int a = 1; // n-1
		int b = 0; // n-2
		for (int i = 0; i < n; i++) {
			if (i > 1) {
				int newA = a + b;
				int newB = a;
				b = newB;
				a = newA;
			}
		}
		return a + b;
	}

	/**
	 * 尾调用优化
	 * @param n
	 * @param curr
	 * @param next
	 * @return
	 */
	public static int fibonacciWithNext(int n, int curr, int next) {
		if (n == 0) {
			return 0;
		}
		if(n==1){
			return next;
		}
		return fibonacciWithNext(n - 1, next, curr + next);
	}

	public static void main(String[] args) {
		System.out.println(fibonacciUseCache(15));
		System.out.println(fibonacciDynamic(15));
		System.out.println(fibonacciDynamic2(15));
		System.out.println(fibonacciWithNext(15, 0, 1));
	}

}


生成一个可逆的短编码

/**
     * 生成一个短的编号
     * @param $input
     * @param int $neededLength
     * @param string $alphabet
     * @return string
     */
    public function gen_short_id($input, $neededLength = 8, $alphabet = '0123456789') {
        $output = '';
        $base = strlen($alphabet);
        if (is_numeric($neededLength)) {
            $neededLength--;
            if ($neededLength > 0) {
                $input += pow($base, $neededLength);
            }
        }
        for ($current = ($input != 0 ? floor(log($input, $base)) : 0); $current >= 0; $current--) {
            $powed = pow($base, $current);
            $floored = floor($input / $powed) % $base;
            $output = $output . substr($alphabet, $floored, 1);
            $input = $input - ($floored * $powed);
        }
        return $output;
    }

    /**
     * 解析一个短的编号
     * @param $input
     * @param int $neededLength
     * @param string $alphabet
     * @return float|int
     */
    public function decode_short_id($input, $neededLength = 8, $alphabet = '0123456789') {
        $output = 0;
        $base = strlen($alphabet);
        $length = strlen($input) - 1;
        for ($current = $length; $current >= 0; $current--) {
            $powed = pow($base, $length - $current);
            $output = ($output + strpos($alphabet, substr($input, $current, 1)) * $powed);
        }
        if (is_numeric($neededLength)) {
            $neededLength--;
            if ($neededLength > 0) {
                $output -= pow($base, $neededLength);
            }
        }
        return $output;
    }

Trie Tree

import java.util.Arrays;

class TrieNode {
	TrieNode[] arr;
	boolean isEnd;
	char val;

	public TrieNode() {
		this.arr = new TrieNode[26];
	}

	public char getVal() {
		return val;
	}

	public void setVal(char val) {
		this.val = val;
	}

	@Override
	public String toString() {
		return "TrieNode [arr=" + Arrays.toString(arr) + ", isEnd=" + isEnd + ", val=" + val + "]";
	}
}

public class Trie {
	private TrieNode root;

	public Trie() {
		root = new TrieNode();
	}

	/**
	 * 构造树节点
	 * @param word
	 */
	public void insert(String word) {
		TrieNode p = root;
		for (int i = 0; i < word.length(); i++) {
			char c = word.charAt(i);
			int index = c - 'a';
			if (p.arr[index] == null) {
				TrieNode temp = new TrieNode();
				temp.setVal(c);
				p.arr[index] = temp;
				p = temp;
			} else {
				p = p.arr[index];
			}
		}
		p.isEnd = true;
	}

	public boolean search(String word) {
		TrieNode p = searchNode(word);
		if (p == null) {
			return false;
		} else {
			if (p.isEnd)
				return true;
		}

		return false;
	}

	public boolean startWith(String prefix) {
		TrieNode p = searchNode(prefix);
		if (p == null) {
			return false;
		} else {
			return true;
		}
	}

	public TrieNode searchNode(String s) {
		TrieNode p = root;
		for (int i = 0; i < s.length(); i++) {
			char c = s.charAt(i);
			int index = c - 'a';
			if (p.arr[index] != null) {
				p = p.arr[index];
			} else {
				return null;
			}
		}

		if (p == root)
			return null;

		return p;
	}

	public static void main(String[] args) {
		Trie trie = new Trie();
		trie.insert("and");
		trie.insert("hello");
		trie.insert("world");
		System.out.println(trie.startWith("he"));
		TrieNode node = trie.searchNode("h");
		System.out.println(node);

	}

}

二叉树相关算法

package test;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

/**
 * 
 * 1.完全二叉树:若二叉树的高度是h,除第h层之外,其他(1~h-1)层的节点数都达到了最大个数,并且第h层的节点都连续的集中在最左边。想到点什么没?实际上,完全二叉树和堆联系比较紧密哈~~~
 * 
 * 2.满二叉树:除最后一层外,每一层上的所有节点都有两个子节点,最后一层都是叶子节点。
 * 
 * 3.哈夫曼树:给定n个权值作为n的叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman
 * tree)。
 * 
 * 4.二叉排序树:又称二叉查找树(Binary Search Tree),亦称二叉搜索树。二叉排序树或者是一棵空树,或者是具有下列性质的二叉树:
 * 若左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若右子树不空,则右子树上所有结点的值均大于或等于它的根结点的值;
 * 左、右子树也分别为二叉排序树; 没有键值相等的节点 二分查找的时间复杂度是O(log(n)),最坏情况下的时间复杂度是O(n)(相当于顺序查找)
 * 
 * 5.平衡二叉树:又称 AVL 树。平衡二叉树是二叉搜索树的进化版,所谓平衡二叉树指的是,左右两个子树的高度差的绝对值不超过 1。
 * 
 * 6.红黑树:红黑树是每个节点都带颜色的树,节点颜色或是红色或是黑色,红黑树是一种查找树。红黑树有一个重要的性质,从根节点到叶子节点的最长的路径不多于最短的路径的长度的两倍。对于红黑树,插入,删除,查找的复杂度都是O(log
 * N)。
 * 
 * @author shichaopeng
 *
 */
public class TestTree {

	/**
	 * 求二叉树中的节点个数 (1)如果二叉树为空,节点个数为0 (2)如果不为空,二叉树节点个数 = 左子树节点个数 + 右子树节点个数 + 1
	 * 
	 * @param root
	 * @return
	 */
	public int getNodeNumRec(TreeNode root) {
		if (root == null) {
			return 0;
		}
		return getNodeNumRec(root.left) + getNodeNumRec(root.right) + 1;
	}

	/**
	 * 求二叉树的最大层数(最大深度) (1)如果二叉树为空,二叉树的深度为0 (2)如果二叉树不为空,二叉树的深度 = max(左子树深度,右子树深度)
	 * + 1
	 * 
	 * @param root
	 * @return
	 */
	public int maxDepth(TreeNode root) {
		if (root == null)
			return 0;
		return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
	}

	/**
	 * 二叉树的最小深度 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
	 * 
	 * @param root
	 * @return
	 */
	public int minDepth(TreeNode root) {
		if (root == null)
			return 0;
		int left = minDepth(root.left);
		int right = minDepth(root.right);
		return (left == 0 || right == 0) ? left + right + 1 : Math.min(left, right) + 1;
	}

	/**
	 * 先序遍历/前序遍历 给定二叉树,返回其节点值的前序遍历。 根 - 左 - 右
	 * 
	 * @param root
	 * @return
	 */
	ArrayList<Integer> preOrderReverse(TreeNode root) {
		ArrayList<Integer> result = new ArrayList<Integer>();
		preOrder(root, result);
		return result;
	}

	void preOrder(TreeNode root, ArrayList<Integer> result) {
		if (root == null) {
			return;
		}
		result.add(root.val);
		preOrder(root.left, result);
		preOrder(root.right, result);
	}

	/**
	 * 先序遍历/前序遍历 非递归 1
	 * 
	 * @param root
	 * @return
	 */
	public List<Integer> preorderTraversal(TreeNode root) {
		LinkedList<Integer> res = new LinkedList<>();
		if (root == null)
			return res;
		Stack<TreeNode> stack = new Stack<>();
		stack.push(root);
		while (!stack.isEmpty()) {
			TreeNode node = stack.pop();
			res.add(node.val);
			if (node.right != null) {
				stack.push(node.right);
			}
			if (node.left != null) {
				stack.push(node.left);
			}
		}
		return res;
	}

	/**
	 * 先序遍历/前序遍历 非递归 2
	 * 
	 * @param root
	 * @return
	 */
	public List<Integer> preorderTraversal2(TreeNode root) {
		List<Integer> res = new ArrayList<Integer>();
		if (root == null)
			return res;
		Stack<TreeNode> stack = new Stack<TreeNode>();
		TreeNode cur = root;
		while (cur != null || !stack.isEmpty()) {
			if (cur != null) {
				res.add(cur.val);
				stack.push(cur);
				cur = cur.left;
			} else {
				cur = stack.pop();
				cur = cur.right;
			}
		}
		return res;
	}

	/**
	 * 给定二叉树,返回其节点值的中序遍历。 左 - 根 - 右
	 * 
	 * @param root
	 * @param result
	 */
	void inOrder(TreeNode root, ArrayList<Integer> result) {
		if (root == null) {
			return;
		}
		preOrder(root.left, result);
		result.add(root.val);
		preOrder(root.right, result);
	}

	/**
	 * 给定二叉树,返回其节点值的中序遍历。 非递归
	 * 
	 * @param root
	 * @return
	 */
	public List<Integer> inorderTraversal(TreeNode root) {
		List<Integer> res = new ArrayList<Integer>();
		if (root == null)
			return res;

		Stack<TreeNode> stack = new Stack<TreeNode>();
		TreeNode cur = root;
		while (!stack.isEmpty() || cur != null) {
			if (cur != null) {
				stack.push(cur);
				cur = cur.left;
			} else {
				cur = stack.pop();
				res.add(cur.val);
				cur = cur.right;
			}
		}
		return res;
	}

	/**
	 * 后序遍历 左 - 右 - 根 给定二叉树,返回其节点值的后序遍历
	 * 
	 * @param root
	 * @param result
	 */
	void postOrder(TreeNode root, ArrayList<Integer> result) {
		if (root == null) {
			return;
		}
		preOrder(root.left, result);
		preOrder(root.right, result);
		result.add(root.val);
	}

	/**
	 * 后序遍历 非递归 1
	 * 
	 * @param root
	 * @return
	 */
	public List<Integer> postorderTraversal(TreeNode root) {
		LinkedList<Integer> ans = new LinkedList<>();
		Stack<TreeNode> stack = new Stack<>();
		if (root == null)
			return ans;

		stack.push(root);
		while (!stack.isEmpty()) {
			TreeNode cur = stack.pop();
			// 采用逆序插入的方式
			ans.addFirst(cur.val);
			if (cur.left != null) {
				stack.push(cur.left);
			}
			if (cur.right != null) {
				stack.push(cur.right);
			}
		}
		return ans;
	}

	/**
	 * 后序遍历 非递归 2
	 * 
	 * @param root
	 * @return
	 */
	public List<Integer> postorderTraversal2(TreeNode root) {
		List<Integer> res = new ArrayList<Integer>();

		if (root == null)
			return res;

		Stack<TreeNode> stack = new Stack<TreeNode>();
		TreeNode cur = root;
		TreeNode visited = null;
		while (!stack.isEmpty() || cur != null) {
			if (cur != null) {
				stack.push(cur);
				cur = cur.left;
			} else {
				cur = stack.peek();
				if (cur.right != null && cur.right != visited) {
					cur = cur.right;
				} else {
					res.add(cur.val);
					visited = cur;
					stack.pop();
					cur = null;
				}
			}
		}
		return res;
	}

	/**
	 * 后序遍历 非递归 3
	 * 
	 * @param root
	 * @return
	 */
	public List<Integer> postorderTraversal3(TreeNode root) {
		LinkedList<Integer> result = new LinkedList<>();
		Deque<TreeNode> stack = new ArrayDeque<>();
		TreeNode p = root;
		while (!stack.isEmpty() || p != null) {
			if (p != null) {
				stack.push(p);
				result.addFirst(p.val); // Reverse the process of preorder
				p = p.right; // Reverse the process of preorder
			} else {
				TreeNode node = stack.pop();
				p = node.left; // Reverse the process of preorder
			}
		}
		return result;
	}

	/**
	 * 分层遍历
	 * 
	 * 给定二叉树,返回其节点值的级别顺序遍历
	 * 
	 * @param root
	 * @return
	 */
	public List<List<Integer>> levelOrder(TreeNode root) {
		List<List<Integer>> res = new ArrayList<List<Integer>>();
		if (root == null)
			return res;

		Queue<TreeNode> queue = new LinkedList<TreeNode>();
		TreeNode cur = null;
		queue.add(root);

		while (!queue.isEmpty()) {
			ArrayList<Integer> level = new ArrayList<Integer>();
			int l = queue.size();
			for (int i = 0; i < l; i++) {
				cur = queue.poll();
				level.add(cur.val);
				if (cur.left != null)
					queue.add(cur.left);
				if (cur.right != null)
					queue.add(cur.right);
			}
			res.add(level);
		}
		return res;
	}

	/**
	 * 
	 * 自下而上分层遍历 给定二叉树,返回其节点值的自下而上级别顺序遍历
	 * 
	 * @param root
	 * @return
	 */
	public List<List<Integer>> levelOrderBottom(TreeNode root) {
		List<List<Integer>> res = new LinkedList<>();
		Queue<TreeNode> queue = new LinkedList<>();
		if (root == null)
			return res;
		queue.add(root);
		while (!queue.isEmpty()) {
			int count = queue.size();
			List<Integer> temp = new LinkedList<>();
			for (int i = 0; i < count; i++) {
				TreeNode node = queue.poll();
				temp.add(node.val);
				if (node.left != null)
					queue.add(node.left);
				if (node.right != null)
					queue.add(node.right);
			}
			// 每次都添加到第一个位置
			res.add(0, temp);
		}
		return res;
	}

	/**
	 * 
	 * 按之字形顺序打印二叉树
	 * 请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。
	 * 
	 * 设两个栈,s2存放奇数层,s1存放偶数层 遍历s2节点的同时按照左子树、右子树的顺序加入s1, 遍历s1节点的同时按照右子树、左子树的顺序加入s2
	 * 
	 * @param pRoot
	 * @return
	 */
	public ArrayList<ArrayList<Integer>> print(TreeNode pRoot) {
		ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
		Stack<TreeNode> s1 = new Stack<TreeNode>();
		Stack<TreeNode> s2 = new Stack<TreeNode>();
		int flag = 1;
		if (pRoot == null)
			return res;
		s2.push(pRoot);
		ArrayList<Integer> temp = new ArrayList<Integer>();
		while (!s1.isEmpty() || !s2.isEmpty()) {
			if (flag % 2 != 0) {
				while (!s2.isEmpty()) {
					TreeNode node = s2.pop();
					temp.add(node.val);
					if (node.left != null) {
						s1.push(node.left);
					}
					if (node.right != null) {
						s1.push(node.right);
					}
				}
			}
			if (flag % 2 == 0) {
				while (!s1.isEmpty()) {
					TreeNode node = s1.pop();
					temp.add(node.val);
					if (node.right != null) {
						s2.push(node.right);
					}
					if (node.left != null) {
						s2.push(node.left);
					}
				}
			}
			res.add(new ArrayList<Integer>(temp));
			temp.clear();
			flag++;
		}
		return res;
	}

	/**
	 * 求二叉树第K层的节点个数
	 * 
	 * @param root
	 * @param k
	 * @return
	 */
	int getKLevelNumber(TreeNode root, int k) {
		if (root == null || k <= 0) {
			return 0;
		}
		if (root != null && k == 1) {
			return 1;
		}
		return getKLevelNumber(root.left, k - 1) + getKLevelNumber(root.right, k - 1);
	}

	/**
	 * 求二叉树第K层的叶子节点个数
	 * 
	 * @param root
	 * @param k
	 * @return
	 */
	int getLLevelLeafNumber(TreeNode root, int k) {
		if (root == null || k <= 0) {
			return 0;
		}
		if (root != null && k == 1) {
			if (root.left == null && root.right == null)
				return 1;
			else
				return 0;
		}
		return getLLevelLeafNumber(root.left, k - 1) + getLLevelLeafNumber(root.right, k - 1);
	}

	/**
	 * 判断两棵二叉树是否结构相同 给定两个二叉树,编写一个函数来检查它们是否相同。
	 * 
	 * 递归解法: (1)如果两棵二叉树都为空,返回真 (2)如果两棵二叉树一棵为空,另一棵不为空,返回假
	 * (3)如果两棵二叉树都不为空,如果对应的左子树和右子树都同构返回真,其他返回假
	 * 
	 * @param p
	 * @param q
	 * @return
	 */
	public boolean isSameTree(TreeNode p, TreeNode q) {
		if (p == null && q == null)
			return true;
		if (p == null || q == null)
			return false;
		if (p.val == q.val)
			return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
		return false;
	}

	/**
	 * 判断二叉树是不是平衡二叉树 给定二叉树,确定它是否是高度平衡的。
	 * 
	 * 对于此问题,高度平衡二叉树定义为:一个二叉树,其中每个节点的两个子树的深度差不相差超过1。
	 * 
	 * 递归解法: (1)如果二叉树为空,返回真
	 * (2)如果二叉树不为空,如果左子树和右子树高度相差不大于1且左子树和右子树都是AVL树,返回真,其他返回假
	 * 
	 * @param root
	 * @return
	 */
	public boolean isBalanced(TreeNode root) {
		if (root == null)
			return true;
		return Math.abs(maxHigh(root.left) - maxHigh(root.right)) <= 1 && isBalanced(root.left)
				&& isBalanced(root.right);
	}

	public int maxHigh(TreeNode root) {
		if (root == null)
			return 0;
		return Math.max(maxHigh(root.left), maxHigh(root.right)) + 1;
	}

	/**
	 * 反转二叉树
	 * 
	 * @param root
	 * @return
	 */
	public TreeNode invertTree(TreeNode root) {
		if (root == null)
			return root;

		TreeNode node = root.left;
		root.left = invertTree(root.right);
		root.right = invertTree(node);

		return root;
	}

	/**
	 * 对称二叉树
	 * 
	 * 给定一个二叉树,检查它是否是镜像对称的。
	 * 
	 * @param root
	 * @return
	 */
	public boolean isSymmetric(TreeNode root) {
		return root == null || isSymmetricHelper(root.left, root.right);
	}

	public boolean isSymmetricHelper(TreeNode left, TreeNode right) {
		if (left == null && right == null)
			return true;
		if (left == null || right == null)
			return false;
		if (left.val != right.val)
			return false;
		return isSymmetricHelper(left.left, right.right) && isSymmetricHelper(left.right, right.left);
	}

	/**
	 * 求二叉树中两个节点的最低公共祖先节点
	 * 
	 * 给定二叉树,找到树中两个给定节点的最低共同祖先(LCA)。
	 * 
	 * 递归解法: (1)如果两个节点分别在根节点的左子树和右子树,则返回根节点
	 * (2)如果两个节点都在左子树,则递归处理左子树;如果两个节点都在右子树,则递归处理右子树
	 * 
	 * @param root
	 * @param p
	 * @param q
	 * @return
	 */
	public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
		if (root == null || root == p || root == q)
			return root;
		TreeNode left = lowestCommonAncestor(root.left, p, q);
		TreeNode right = lowestCommonAncestor(root.right, p, q);
		if (left != null && right != null)
			return root;
		return left == null ? right : left;
	}

	/**
	 * 求二叉搜索树的最近公共祖先
	 * 
	 * 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点
	 * p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”
	 * 
	 * 注意二叉搜索树的特性:左子树 < 根节点 < 右子树
	 * 
	 * @param root
	 * @param p
	 * @param q
	 * @return
	 */
	public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
		if (root.val > p.val && root.val > q.val) {
			return lowestCommonAncestor(root.left, p, q);
		} else if (root.val < p.val && root.val < q.val) {
			return lowestCommonAncestor(root.right, p, q);
		} else {
			return root;
		}
	}

	int path = 0;

	/**
	 * 求二叉树的直径
	 * 
	 * 给定一棵二叉树,你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。
	 * 
	 * 递归解法:对于每个节点,它的最长路径等于左子树的最长路径+右子树的最长路径
	 * 
	 * @param root
	 * @return
	 */
	public int diameterOfBinaryTree(TreeNode root) {
		diamHelper(root);
		return path;
	}

	private int diamHelper(TreeNode root) {
		if (root == null)
			return 0;
		int left = diamHelper(root.left);
		int right = diamHelper(root.right);
		path = Math.max(path, left + right);
		return Math.max(left, right) + 1;
	}

	/**
	 * 由前序遍历序列和中序遍历序列重建二叉树
	 * 
	 * 根据一棵树的前序遍历与中序遍历构造二叉树。
	 * 
	 * @param preorder
	 * @param inorder
	 * @return
	 */
	public TreeNode buildTree1(int[] preorder, int[] inorder) {
		if (preorder.length == 0 || inorder.length == 0)
			return null;
		return buildTreeHelper1(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
	}

	public TreeNode buildTreeHelper1(int[] preorder, int pre_start, int pre_end, int[] inorder, int in_start,
			int in_end) {
		if (pre_start > pre_end || in_start > in_end)
			return null;
		TreeNode root = new TreeNode(preorder[pre_start]);
		for (int i = in_start; i <= in_end; i++) {
			if (inorder[i] == preorder[pre_start]) {
				// 左子树的长度:i-is
				root.left = buildTreeHelper1(preorder, pre_start + 1, pre_start + i - in_start, inorder, in_start,
						i - 1);
				root.right = buildTreeHelper1(preorder, pre_start + i - in_start + 1, pre_end, inorder, i + 1, in_end);
			}
		}
		return root;
	}

	/**
	 * 从中序与后序遍历序列构造二叉树
	 * 
	 * 根据一棵树的中序遍历与后序遍历构造二叉树。
	 * 
	 * 本题与“从前序与中序遍历序列构造二叉树”是一个套路。
	 * 
	 * 唯一的区别是,后序序列的最后一个节点是根节点,因此我们要从后序序列的最后一个节点入手,再去中序序列中找到这个节点。
	 * 
	 * 在这个节点左侧的属于根节点的左子树部分,右侧的属于根节点右子树部分。
	 * 
	 * 然后根据左右子树节点的数量,在后序序列中找到他们各自的后序序列。
	 * 
	 * 比左子树节点个数为5,那么在后序序列中前五个节点就是左子树节点,之后的节点除了最后一个节点都是右子树节点。
	 * 
	 * @param inorder
	 * @param postorder
	 * @return
	 */
	public TreeNode buildTree2(int[] inorder, int[] postorder) {
		if (inorder.length == 0 || postorder.length == 0)
			return null;
		return buildTreeHelper2(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
	}

	public TreeNode buildTreeHelper2(int[] inorder, int in_start, int in_end, int[] postorder, int post_start,
			int post_end) {
		if (in_start > in_end || post_start > post_end)
			return null;
		TreeNode root = new TreeNode(postorder[post_end]);
		for (int i = in_start; i <= in_end; i++) {
			if (inorder[i] == postorder[post_end]) {
				root.left = buildTreeHelper2(inorder, in_start, i - 1, postorder, post_start,
						post_start + i - in_start - 1);
				root.right = buildTreeHelper2(inorder, i + 1, in_end, postorder, post_start + i - in_start,
						post_end - 1);
			}
		}
		return root;
	}

	/**
	 * 判断二叉树是不是完全二叉树
	 * 
	 * 完全二叉树是指最后一层左边是满的,右边可能慢也不能不满,然后其余层都是满的,根据这个特性,利用层遍历。如果我们当前遍历到了NULL结点,如果后续还有非NULL结点,说明是非完全二叉树。
	 * 
	 * @param root
	 * @return
	 */
	public boolean checkCompleteTree(TreeNode root) {
		boolean flag = false;
		Queue<TreeNode> queue = new LinkedList<TreeNode>();
		if (root == null)
			return true;
		queue.add(root);
		while (!queue.isEmpty()) {
			TreeNode node = queue.poll();
			if (node != null) {
				if (flag == true)
					return false;
				queue.add(node.left);
				queue.add(node.right);
			} else {
				flag = true;
			}
		}
		return true;
	}

	/**
	 * 输入两棵二叉树A,B,判断B是不是A的子结构。
	 * 
	 * @param root1
	 * @param root2
	 * @return
	 */
	public boolean hasSubtree(TreeNode root1, TreeNode root2) {
		if (root1 == null || root2 == null) {
			return false;
		}
		return isSubtree(root1, root2) || hasSubtree(root1.left, root2) || hasSubtree(root1.right, root2);
	}

	public boolean isSubtree(TreeNode root1, TreeNode root2) {
		// 要先判断root2, 不然{8,8,7,9,2,#,#,#,#,4,7},{8,9,2}这个测试用例通不过。
		if (root2 == null)
			return true;
		if (root1 == null)
			return false;
		if (root1.val == root2.val) {
			return isSubtree(root1.left, root2.left) && isSubtree(root1.right, root2.right);
		} else
			return false;
	}

	ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
	ArrayList<Integer> temp = new ArrayList<Integer>();

	/**
	 * 二叉树中和为某一值的路径
	 * 
	 * 输入一颗二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。
	 * 
	 * 路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
	 * 
	 * @param root
	 * @param target
	 * @return
	 */
	public ArrayList<ArrayList<Integer>> findPath(TreeNode root, int target) {
		if (root == null)
			return res;
		target -= root.val;
		temp.add(root.val);
		if (target == 0 && root.left == null && root.right == null)
			res.add(new ArrayList<Integer>(temp));
		else {
			findPath(root.left, target);
			findPath(root.right, target);
		}
		temp.remove(temp.size() - 1);
		return res;
	}

	/**
	 * 
	 * 二叉树的下一个结点
	 * 
	 * 给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针。
	 * 
	 * @param pNode
	 * @return
	 */
	public TreeLinkNode getNext(TreeLinkNode pNode) {
		if (pNode == null) {
			return null;
		}
		if (pNode.right != null) {
			TreeLinkNode node = pNode.right;
			while (node.left != null) {
				node = node.left;
			}
			return node;
		}
		while (pNode.next != null) {
			TreeLinkNode root = pNode.next;
			if (pNode == root.left)
				return root;
			pNode = root;
		}
		return null;
	}

	// Encodes a tree to a single string.
	public String serialize(TreeNode root) {
		if (root == null)
			return "#,";
		StringBuffer res = new StringBuffer(root.val + ",");
		res.append(serialize(root.left));
		res.append(serialize(root.right));
		return res.toString();
	}

	// Decodes your encoded data to tree.
	public TreeNode deserialize(String data) {
		String[] d = data.split(",");
		Queue<String> queue = new LinkedList<>();
		for (int i = 0; i < d.length; i++) {
			queue.offer(d[i]);
		}
		return pre(queue);
	}

	public TreeNode pre(Queue<String> queue) {
		String val = queue.poll();
		if (val.equals("#"))
			return null;
		TreeNode node = new TreeNode(Integer.parseInt(val));
		node.left = pre(queue);
		node.right = pre(queue);
		return node;
	}
}

class TreeLinkNode {
	int val;
	TreeLinkNode left;
	TreeLinkNode right;
	TreeLinkNode next;

	TreeLinkNode(int x) {
		val = x;
	}
}

class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;

	TreeNode(int x) {
		val = x;
	}
}


反转链表


/**
 * 输入一个链表,反转链表后,输出新链表的表头。
 * 
 * 设置三个指针,head为当前节点,pre为当前节点的前一个节点,next为当前节点的下一个节点,
 * 
 * 需要pre和next的目的是让当前节点从pre->head->next1->next2
 * 
 * 变成pre<-head next1->next2的过程中,
 * 
 * 用pre让节点反转所指方向,next节点保存next1节点防止链表断开
 * 
 * 
 * 需要注意的点: 1、如果输入的头结点是null,则返回null 2、链表断裂的考虑
 * 
 * @author shichaopeng
 *
 */
public class TestReverse {

	public ListNode ReverseList(ListNode head) {
		if (head == null)
			return null;
		ListNode pre = null;
		ListNode next = null;

		while (head != null) {
			next = head.next;
			head.next = pre;
			pre = head;
			head = next;
		}
		return pre;
	}
}

class ListNode {
	int val;
	ListNode next = null;

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