參考兩篇其他bolg總結(jié)的二叉樹：
https://github.com/xy7313/lintcode/blob/master/L3-BinaryTree/aboutTree.java
1. 樹和分治法的關(guān)系
- 分治法：divide-conquer
- 算法題目中，很大部分的樹題都可以用分治法的方法來解決
- 關(guān)于樹的題目比如
- Traverse in Binary tree: Preorder/Inorder/Postorder
前序遍歷（Pre-Order）：根節(jié)點(diǎn)->左子樹->右子樹(NLR)
中序遍歷（In-Order）：左子樹->根節(jié)點(diǎn)->右子樹(LNR)
后序遍歷（Post-Order）：左子樹->右子樹->根節(jié)點(diǎn)(LRN)舉個(gè)例子桑驱，比如中序的時(shí)候索烹，從以d為root的最下面子樹開始花竞，沒有左子樹，所以d嗓化，e，之后遍歷以b為root的子樹，應(yīng)該是b煌集，f，但f也是root捌省，所以這時(shí)候不到f苫纤，而是g，之后才f
中序纲缓，左中右的時(shí)候卷拘，如果該右節(jié)點(diǎn)了，右節(jié)點(diǎn)有子節(jié)點(diǎn)祝高，先去子節(jié)點(diǎn)栗弟，但是前序就是，該誰就先寫上工闺，之后再看他的子節(jié)點(diǎn)
leetcode-solution-java傳送門(github)(解析在文件夾下readme中)：
postorder
preorder
inorder
my gist 代碼答案?jìng)魉烷T(go)：
preorder
inorder
DFS in Binary Tree（BFS : non-recursive）
Basic operations on Binary Tree: Insert/Remove/Find/Validate
解決這些樹的搜索乍赫，遍歷颓屑，操作問題的方法：
non-recursive : iteration,
recursive : traverse, 全局，遞歸開始狀態(tài)是當(dāng)前狀態(tài)耿焊。但是全局變量有缺點(diǎn)揪惦，比如占內(nèi)存；全局內(nèi)可修改罗侯，易出錯(cuò)
preorder下遞歸三要素：
1. 遞歸的定義：把root為根的proorder放入result
2. 遞歸結(jié)束的時(shí)候器腋，該root的樹節(jié)點(diǎn)都加入了，當(dāng)前為null了
3. 遞歸的拆解：放root钩杰。放左子樹纫塌，放右子樹
- recursive : divide conquer。分治讲弄，沒有全局的變量措左，（自己本身就是遞歸的一部分）1. 分；2. 合
*. other diffs between traverse and divide-conquer:
1. result in parameter vs result in return value
2. top down vs bottom up
- basic code of preorder, inorder, postorder 包括4中講的三種方法的實(shí)現(xiàn)
2. 復(fù)雜度分析
- tree problem time complexity:
二叉樹通用時(shí)間復(fù)雜度計(jì)算公式 =（二叉樹的節(jié)點(diǎn)個(gè)數(shù)n * 每個(gè)節(jié)點(diǎn)的處理時(shí)間）
比如divide conquer中都是if避除，處理時(shí)間就是O(1)怎披，總共就是O(n)
notice!! only complete binary tree is logn, others , n/h - 時(shí)間復(fù)雜度分析方法
上篇回顧： - binary search: 通過O(1)的時(shí)間，把規(guī)模為n的問題變?yōu)閚/2
T(n)=T(n/2)+O(1)
=T(n/4)+O(1)+O(1)
…
=T(1)+logn*O(1)
==> O(logn)
- more: 思考:通過O(n)的時(shí)間瓶摆，把規(guī)模為n的問題變?yōu)閚/2?
T(n)=T(n/2)+O(n)
=T(n/4)+O(n)+O(n/2) 這里不能把O(n/2)約成O(n)凉逛，之后再約
…
=T(1)+O(n+n/2+n/4+…)
=T(1)+O(2n)
*因?yàn)椋?+2+4+8+…+n
=2+2+4+…+n-1
=2n
==>O(n)
本節(jié)兩個(gè)延伸問題：
- 通過O(n)的時(shí)間，把n的問題群井，變?yōu)榱藘蓚€(gè)n/2的問題状飞，復(fù)雜度是多少? （比如：quick sort代芜， merge sort）
T(n)=2 * T(n/2) + O(n)
=2 * (2T(n/4) + O(n/2)) + O(n)
=4 * T(n/4) + 2 * O(n/2) + O(n)
=4 * (2T(n/8) + O(n/4)) + 2 * O(n/2) + O(n)
=8 * T(n/8) + 4 * O(n/4) + 2 * O(n/2) + O(n)
...
=2^k * T(n/2^k)+k * O(n)
k=logn
==>O(nlong) + n * T(1)
=O(nlong)
- 通過O(1)的時(shí)間蓉坎，把n的問題匣距，變成了兩個(gè)n/2的問題钟些，復(fù)雜度是多少?
T(n)=2 * T(n/2) + O(n)
=2 * (2T(n/4) + O(n/2)) + O(1)
=4 * T(n/4) + 2 * O(1) + O(1)
=4 * (2T(n/8) + O(1)) + 2 * O(1) + O(1)
=8 * T(n/8) + 4 * O(1) + 2 * O(1) + O(1)
...
=2^k * T(n/2^k)+(1+2+4+...+2^k) * O(1)
k=logn(下面1+2+4+...上次證明過了)
==>(1+2+4+...+n) * O(1) + n * T(1)
=O(n)+n * T(1)
=O(n)
這個(gè)問題也可以通過畫樹的方式來看，得到第一層樹的時(shí)候做了O(1)的工作鸵荠，得到兩個(gè)n/2炬藤，下一步是做2 * O(1)的工作浙宜，得到4個(gè)n/4稍坯，... 最后還是(1+2+4+...+n) * O(1)得到最終結(jié)果O(1)
3. 解法
- 分析整棵樹在該問題上的結(jié)果 和左右兒子在該問題上的結(jié)果之間的聯(lián)系是什么
- Result類：一般在divide-conquer方法中需要返回一堆東西時(shí)使用：class ResultType { int var1, var2; }
- recursive
遞歸的基本思想是廣義地把規(guī)模大的問題轉(zhuǎn)化為規(guī)模小的相似的子問題或者相似的子問題集合來解決酬荞。廣義針對(duì)規(guī)模的搓劫，規(guī)模的縮小具體可以是指遞歸函數(shù)的參數(shù)瞧哟，也可以是其參數(shù)之一。相似是指解決大問題的方法和解決小問題的方法往往是同一個(gè)方法枪向，還可以是指解決子問題集的各子問題的方法是同一個(gè)方法勤揩。解決大問題的方法可以是由解決次規(guī)模問題的方法和解決剩余部分的方法組成，也可以是由一系列解決次規(guī)模問題的方法組成--http://zisong.me/post/suan-fa/ren-nao-li-jie-di-gui
4. 分類題目總結(jié)
- 比較簡(jiǎn)單的例子秘蛔，用divide-conquer和traverse都可以的：
- 題一：Binary Tree Paths：這個(gè)是兩種方法實(shí)現(xiàn)：兩種方法都是遞歸陨亡，所以都要先判斷root==null和左右節(jié)點(diǎn)==null的情況傍衡，做適合的返回
- divide-conquer: 類似于先找左右子樹的path，然后和root分別組成path负蠕，所以上面說的左右節(jié)點(diǎn)==null的情況要把當(dāng)前節(jié)點(diǎn)加入蛙埂，左右子樹的path也通過該方法獲得，最后把左子樹的所有path遍歷都加入root,右邊同理遮糖，得到path
- traverse:通常是站在root绣的，向左右走，所以root先加入path欲账，走到盡頭的路上一次加入節(jié)點(diǎn)屡江，最后，左右節(jié)點(diǎn)==null的時(shí)候赛不，要把當(dāng)前已生成的path加入到結(jié)果集中惩嘉。
//divide-conquer
public List<String> binaryTreePaths(TreeNode root) {
List<String> paths = new ArrayList<>();
if(root==null) return paths;
if(root.left == null && root.right == null){
paths.add(root.val+"");
return paths;
}
List<String> left =binaryTreePaths(root.left);
List<String> right =binaryTreePaths(root.right);
//left==[], skip for()
for(String l : left){
paths.add(root.val+"->"+l);
}
for(String r : right){
paths.add(root.val+"->"+r);
}
return paths;
}
// helper-traverse
public List<String> binaryTreePaths(TreeNode root) {
List<String> result = new ArrayList<>();
if(root==null) return result;
helper(root,String.valueOf(root.val),result);
return result;
}
private void helper(TreeNode root, String path, List<String> result){
if(root==null) return;
if(root.left == null && root.right == null){
result.add(path);
}
if(root.left!=null){
helper(root.left, path+"->"+String.valueOf(root.left.val), result);
}
if(root.right!=null){
helper(root.right, path+"->"+String.valueOf(root.right.val), result);
}
}
- 題二：Maximum Depth of Binary Tree：左邊取最大，右邊取最大踢故，結(jié)果是這兩者之中的較大值+1（root）文黎，左右兩邊取最大就是遞歸調(diào)用自己，divide-conquer比較簡(jiǎn)單
- 題三：Minimum Subtree：跟上面思路一樣殿较，都取最小臊诊，區(qū)別在于上面是要返回最大值int的，這個(gè)要返回node斜脂，所以用一樣的分治法需要new class, Result{node; min; sum}來存儲(chǔ)我們需要的結(jié)果抓艳。 也可以用traverse+全局變量+divide-conquer的方法做
貼一下這兩個(gè)題的divide-conquer方法
//max depth
public int maxDepth(TreeNode root) {
int dep = 0;
// null or leaf
if (root == null) {
return dep;
}
// Divide
int left = maxDepth(root.left);
int right = maxDepth(root.right);
// Conquer
return Math.max(left,right)+1;
}
// min subtree
public class Solution {
class Result{
int sum;
int min;
TreeNode minroot;
public Result(int sum, TreeNode minroot,int min){
this.sum = sum;
this.minroot=minroot;
this.min = min;
}
}
public TreeNode findSubtree(TreeNode root){
return helper(root).minroot;
}
private Result helper(TreeNode root){
if(root==null) return new Result(0,null,Integer.MAX_VALUE);
//divide
Result left = helper(root.left);
Result right = helper(root.right);
//conquer
Result r = new Result(root.val,root,root.val);
r.sum = root.val+left.sum+right.sum;
if(r.sum<left.min&&r.sum<right.min){
return new Result(r.sum,r.minroot,r.sum);
}else if(r.sum>left.min&&left.min<right.min){
return new Result(r.sum,left.minroot,left.min);
}else{
return new Result(r.sum,right.minroot,right.min);
}
}
}
- 用Result類的一些例子（包括上面的min subtree的方法）
- Balanced Binary Tree
首先看定義：左子樹是平衡的，右子樹是平和的帚戳，左右高度差距不大于1玷或，或者說高度是想同的，三個(gè)條件 - 第一種解法看起來代碼短小精悍片任，很好偏友，但這個(gè)解法最難的地方應(yīng)該是maxdepth這個(gè)方法的返回值部分，最后如果遍歷到目前為止对供，是balanced的話位他，記錄當(dāng)前的height就是通過return語句做的。應(yīng)該是因?yàn)檫@里只要求返回Boolean产场，所以可以省個(gè)Result類
- Result類實(shí)現(xiàn)鹅髓，兩種解法的思路其實(shí)就一樣，寫過第一種京景，第二種就可以自己寫出來了窿冯，需要注意一點(diǎn)的是當(dāng) unbalanced， maxdepth怎么表示合適确徙，我選了0醒串，也可以是-1执桌，可以通過交流來選擇合適的值。
public class Solution {
public boolean isBalanced(TreeNode root) {
return maxDepth(root)!=-1;
}
private int maxDepth(TreeNode root){
if(root==null) return 0;
}
int left = maxDepth(root.left);
int right = maxDepth(root.right);
if(left==-1 || right==-1 || Math.abs(left-right)>1){
return -1;
}
return Max.max(left,right)+1;
}
//with Result class
public class Solution {
class Result{
int maxdepth;
boolean isBalanced;
public Result(boolean isBalanced, int maxdepth){
this.isBalanced = isBalanced;
this.maxdepth = maxdepth;
}
}
public boolean isBalanced(TreeNode root) {
return helper(root).isBalanced;
}
private Result helper(TreeNode root){
if(root==null) return new Result(true,0);
Result left = helper(root.left);
Result right = helper(root.right);
if(!left.isBalanced || !right.isBalanced || Math.abs(left.maxdepth-right.maxdepth)>1){
return new Result(false,0);
}
return new Result(true,Math.max(left.maxdepth,right.maxdepth)+1);
}
}
- Validate Binary Search Tree
一個(gè)traverse方法芜赌，一個(gè)divide conquer仰挣，前者代碼更簡(jiǎn)潔，后者思路更清晰缠沈，要注意一點(diǎn)是validate函數(shù)中如果沒有違背BST規(guī)則的話最后返回的是更新的Result椎木，更新max用right.max, 更新min用left.min不要弄錯(cuò)了
class Result{
boolean is_bst;
int maxValue, minValue;
Result(boolean is_bst, int maxValue, int minValue) {
this.is_bst = is_bst;
this.maxValue = maxValue;
this.minValue = minValue;
}
}
public class Solution {
public boolean isValidBST(TreeNode root) {
Result r = validate(root);
return r.is_bst;
}
private Result validate(TreeNode root){
//要想好這里返回什么
if(root==null ) return new Result(true,Integer.MIN_VALUE,Integer.MAX_VALUE);
Result left = validate(root.left);
Result right = validate(root.right);
if(!left.is_bst || !right.is_bst){
return new Result(false,0,0);
}
if(root.left!=null&& left.maxValue>=root.val){
return new Result(false,0,0);
}
if(root.right!=null&& right.minValue<=root.val){
return new Result(false,0,0);
}
return new Result(true,
Math.max(right.maxValue,root.val),
Math.min(left.minValue,root.val)
);
}
}
- Subtree with Maximum Average
九章答案里只有traverse+divide/conquer的方法，和上面那個(gè)min subtree很類似博烂，在用全局變量的基礎(chǔ)上加入了Result class香椎，全局變量也有一個(gè)是Result 類型。一個(gè)小trick是求ave的時(shí)候用了 轉(zhuǎn)換成乘法的方式禽篱，避免除法帶來的誤差等各種問題
private TreeNode subtree = null;
private ResultType subtreeResult = null;
private class ResultType {
public int sum, size;
public ResultType(int sum, int size) {
this.sum = sum;
this.size = size;
}
}
public TreeNode findSubtree2(TreeNode root) {
helper(root);
return subtree;
}
private ResultType helper(TreeNode root) {
if (root == null) {
return new ResultType(0, 0);
}
ResultType left = helper(root.left);
ResultType right = helper(root.right);
ResultType result = new ResultType(
left.sum + right.sum + root.val,
left.size + right.size + 1
);
if (subtree == null ||
subtreeResult.sum * result.size < result.sum * subtreeResult.size
) {
subtree = root;
subtreeResult = result;
}
return result;
}
Flatten Binary Tree to Linked List
思路是：flattern左子樹和右子樹畜伐，然后root—>left.head, left.tail—>right.head 。就是左子樹flatten躺率，右子樹flatten玛界，那我們想把root，左悼吱，右三部分拼起來就需要root->left.first--left.last->right.first
有三種方法慎框，都看一下Binary Tree Longest Consecutive Sequence (google onsite)
比較簡(jiǎn)單的一種traverse+divide conquer方法:一個(gè)全局變量longest和一個(gè)helper方法
private int helper(TreeNode root, TreeNode parent, int lengthWithoutRoot) {
if (root == null) {
return 0;
}
int length = (parent != null && parent.val + 1 == root.val)
? lengthWithoutRoot + 1
: 1;
int left = helper(root.left, root, length);
int right = helper(root.right, root, length);
return Math.max(length, Math.max(left, right));
}
- LCA系列：給兩個(gè)node A, B 找最近公共祖先
- 新手版，簡(jiǎn)單的divide+conquer后添，因?yàn)檫@里不用管是不是都存在笨枯，所以后面那里直接返回left，right遇西∠诰看起來是種很取巧的方法
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode node1, TreeNode node2) {
if (root == null || root == node1 || root == node2) {
return root;
}
// Divide
TreeNode left = lowestCommonAncestor(root.left, node1, node2);
TreeNode right = lowestCommonAncestor(root.right, node1, node2);
// Conquer
if (left != null && right != null) {
return root;
}
if (left != null) {
return left;
}
if (right != null) {
return right;
}
return null;
}
2. 包含parent指針：找到給定的A，B兩點(diǎn)到root的path粱檀，然后從root開始一起遍歷兩條path洲敢，path上最后一個(gè)相同的點(diǎn)，就是LCA茄蚯。這個(gè)思路很直接
public ParentTreeNode lowestCommonAncestorII(ParentTreeNode root,
ParentTreeNode A,
ParentTreeNode B) {
if(root==null) return null;
ArrayList<ParentTreeNode> left = pathToRoot(A);
ArrayList<ParentTreeNode> right = pathToRoot(B);
int idxl = left.size()-1;
int idxr = right.size()-1;
ParentTreeNode lca = null;
while (idxl >= 0 && idxr >= 0) {
if(left.get(idxl)!=right.get(idxr)) break;
lca = left.get(idxl);
idxl--;
idxr--;
}
return lca;
}
private ArrayList<ParentTreeNode> pathToRoot(ParentTreeNode node){
ArrayList<ParentTreeNode> path = new ArrayList<ParentTreeNode>();
//理解思路情況下這里寫錯(cuò)了压彭，判斷了parent并添加parent，不對(duì)渗常。
while(node!=null ){
path.add(node);
node = node.parent;
}
return path;
}
3. 如果給的節(jié)點(diǎn)有一個(gè)不存在壮不，返回null（新手版返回存在的那個(gè)節(jié)點(diǎn)）這個(gè)方法反正想不到，而且判斷是否存在那里凳谦，很繞忆畅。抄的lintcode答案。尸执。家凯。
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
// check if a exists, b exists
class Result {
public boolean a_exist, b_exist;
public TreeNode node;
Result(boolean a, boolean b, TreeNode n) {
a_exist = a;
b_exist = b;
node = n;
}
}
public class Solution {
public TreeNode lowestCommonAncestor3(TreeNode root, TreeNode A, TreeNode B) {
Result re = help(root,A,B);
if(re.a_exist && re.b_exist) return re.node;
else return null;
}
private Result help(TreeNode root, TreeNode A, TreeNode B){
if(root==null) return new Result(false, false, null);
Result left = help(root.left, A, B);
Result right = help(root.right, A, B);
boolean aexi = left.a_exist || right.a_exist || root==A;
boolean bexi = left.b_exist || right.b_exist || root==B;
if(root==A || root==B || (left.node!=null && right.node!=null)){
return new Result(aexi, bexi, root);
}
if(left.node!=null) return new Result(aexi, bexi, left.node);
if(right.node!=null) return new Result(aexi, bexi, right.node);
return new Result(aexi, bexi, null);
}
}
- Binary Tree Path Sum系列：給一個(gè)target，找root到leaf的一條path和==target
- 正常版
public List<List<Integer>> binaryTreePathSum(TreeNode root, int target) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) {
return result;
}
ArrayList<Integer> path = new ArrayList<Integer>();
//A valid path is from root node to any of the leaf nodes. So we always need to add root in each path.
path.add(root.val);
helper(root, path, root.val, target, result);
return result;
}
//preorder如失、DFS + backtracking
private void helper(TreeNode root,
ArrayList<Integer> path,
int sum,
int target,
List<List<Integer>> result) {
// 遞歸的出口：meet leaf && sum==target
if (root.left == null && root.right == null) {
if (sum == target) {
result.add(new ArrayList<Integer>(path));
}
return;
}
//遞歸的拆解：分別去左右子樹绊诲，用來算sum
if (root.left != null) {
path.add(root.left.val);
helper(root.left, path, sum + root.left.val, target, result);
//back-tracking, delete the last elementm of path to contruct new path
path.remove(path.size() - 1);
}
if (root.right != null) {
path.add(root.right.val);
helper(root.right, path, sum + root.right.val, target, result);
path.remove(path.size() - 1);
}
}
1. The path does not need to start or end at the root or a leaf, but it must go in a straight line down.
思路是：
到每個(gè)點(diǎn)的時(shí)候，都幾下所有到這個(gè)點(diǎn)的path褪贵，包括不從頭出發(fā)的掂之，只要是在當(dāng)前點(diǎn)end的path，都存脆丁。比如1--2--4這樣的樹（請(qǐng)腦補(bǔ)成一棵樹）世舰，走到2, store[[],[2],[1,2]]，同樣的走到4, store [[],[4],[1,2,4],[2,4]]. 其他見代碼注釋槽卫，也是個(gè)自己寫估計(jì)寫不出來的方法
public List<List<Integer>> binaryTreePathSum2(TreeNode root, int target) {
List<List<Integer>> results = new ArrayList<List<Integer>>();
//buffer這名字意味著這個(gè)東西是起輔助作用的,幫助記錄path跟压，從而在得到target的時(shí)候可以在buffer中倒推找到validpath
ArrayList<Integer> buffer = new ArrayList<Integer>();
if (root == null)
return results;
findSum(root, target, buffer, 0, results);
return results;
}
//遞歸的定義：level的意思顯而易見，但不太知道為什么用level
public void findSum(TreeNode head, int sum, ArrayList<Integer> buffer, int level, List<List<Integer>> results) {
if (head == null) return;
//因?yàn)楹竺孢€要傳入sum歼培，所以copy一個(gè)sum值來操作而不在原數(shù)據(jù)上操作震蒋。這里對(duì)tmp sum的操作是-=，target-=nodes.vals直到等于0時(shí)躲庄，就說明這幾個(gè)nodes sum==target
int tmp = sum;
buffer.add(head.val);
for (int i = level;i >= 0; i--) {
tmp -= buffer.get(i);
if (tmp == 0) {
//在buf中回找validPath
List<Integer> validPath = new ArrayList<Integer>();
for (int j = i; j <= level; ++j)
validPath.add(buffer.get(j));
results.add(validPath);
}
}
findSum(head.left, sum, buffer, level + 1, results);
findSum(head.right, sum, buffer, level + 1, results);
buffer.remove(buffer.size() - 1);
}
2. the path could be start and end at any node in the tree.（n個(gè)節(jié)點(diǎn)的樹查剖，任意兩點(diǎn)選路徑共有n choose 2條，可以暴力解噪窘，枚舉所有兩點(diǎn)之間有路徑的情況笋庄，以當(dāng)前點(diǎn)分左右所有節(jié)點(diǎn)兩部分，兩部分兩兩配對(duì)）
可以拐彎的follow-up倔监，關(guān)注點(diǎn)都在拐點(diǎn)无切，拐點(diǎn)前后，必是直上直下丐枉，所以可以用正常方法得到哆键，之后在拼接(代碼自己并不能獨(dú)立寫，不貼了)
5. 樹和分治總結(jié)
二叉樹
給出一棵Binary Tree的字符串表示瘦锹，比如[1,[2,3]]籍嘹，還原這棵二叉樹（高頻）
給出一棵Binary Tree的先序和中序遍歷序列，還原這棵二叉樹
給出一棵Binary Tree弯院，按照深度（同樣深度從左往右）遍歷并輸出結(jié)果
給出一棵Binary Tree辱士，輸出每一條從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑
給出一棵Binary Tree，輸出與之鏡面對(duì)稱的二叉樹
給出兩棵Binary Tree听绳，判斷這兩棵二叉樹是否完全一樣（形狀和每個(gè)點(diǎn)的value都要相同才算完全一樣）
給出兩棵Binary Tree颂碘，A和B，判斷B是否為A的子樹
分治法
求一棵二叉樹的最大深度（分治思想的簡(jiǎn)單應(yīng)用）
給出一棵Binary Tree椅挣，求出這棵二叉樹上和最大的路徑
給出一棵Binary Search Tree头岔，問是否是Balanced Binary Search Tree
合并k個(gè)排好序的List（高頻）
求一個(gè)Array中的中位數(shù)（高頻塔拳，partition方法）
給出兩個(gè)排好序的List，輸出這兩個(gè)序列中的中位數(shù)峡竣，如果存在兩個(gè)中位數(shù)則輸出這兩個(gè)數(shù)的平均數(shù)
給出一個(gè)Array靠抑，求出Array中的每個(gè)元素的右邊比其小的元素個(gè)數(shù)（歸并排序應(yīng)用）
給出一個(gè)平面上的若干個(gè)點(diǎn)，求其中最近的兩個(gè)點(diǎn)的距離（要求時(shí)間復(fù)雜度小于n^2）
給出一個(gè)n*n的棋盤适掰，n是2的冪颂碧，開始時(shí)這個(gè)棋盤上只有一個(gè)格子是黑色的，其他均是白色的±嗬耍現(xiàn)在需要用一個(gè)黑色的L型去填滿這個(gè)棋盤载城，求一種填滿的方案（要求時(shí)間復(fù)雜度盡可能低）
Reference
6. 其他相關(guān)問題
? Binary Search Tree Iterator
? http://www.lintcode.com/problem/binary-search-tree-iterator
? http://www.jiuzhang.com/solutions/binary-search-tree-iterator
? In-order Successor in Binary Search Tree
? http://www.lintcode.com/problem/inorder-successor-in-binary-search-tree/
? http://www.jiuzhang.com/solutions/inorder-successor-in-binary-search-tree/
? Search Range in Binary Search Tree
? http://www.lintcode.com/problem/search-range-in-binary-search-tree/
? Insert Node in a Binary Search Tree
? http://www.lintcode.com/problem/insert-node-in-a-binary-search-tree/
? Remove Node in a Binary Search Tree
? http://www.lintcode.com/problem/remove-node-in-binary-search-tree/
? http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/BST-delete.html
- 求二叉樹中的節(jié)點(diǎn)個(gè)數(shù):
getNodeNumRec（遞歸），getNodeNum（迭代） - 求二叉樹的深度:
getDepthRec（遞歸）费就，getDepth - 分層遍歷二叉樹（按層次從上往下诉瓦，從左往右）:
levelTraversal, levelTraversalRec（遞歸解法） - 將二叉查找樹變?yōu)橛行虻碾p向鏈表:
convertBST2DLLRec, convertBST2DLL
如果二叉查找樹不為空：
如果左子樹為空，對(duì)應(yīng)雙向有序鏈表的第一個(gè)節(jié)點(diǎn)是根節(jié)點(diǎn)受楼，左邊不需要其他操作垦搬；
如果左子樹不為空，轉(zhuǎn)換左子樹艳汽，二叉查找樹對(duì)應(yīng)雙向有序鏈表的第一個(gè)節(jié)點(diǎn)就是左子樹轉(zhuǎn)換后雙向有序鏈表的第一個(gè)節(jié)點(diǎn)猴贰，同時(shí)將根節(jié)點(diǎn)和左子樹轉(zhuǎn)換后的雙向有序鏈 表的最后一個(gè)節(jié)點(diǎn)連接；
如果右子樹為空河狐，對(duì)應(yīng)雙向有序鏈表的最后一個(gè)節(jié)點(diǎn)是根節(jié)點(diǎn)米绕，右邊不需要其他操作；
如果右子樹不為空馋艺，對(duì)應(yīng)雙向有序鏈表的最后一個(gè)節(jié)點(diǎn)就是右子樹轉(zhuǎn)換后雙向有序鏈表的最后一個(gè)節(jié)點(diǎn)栅干，同時(shí)將根節(jié)點(diǎn)和右子樹轉(zhuǎn)換后的雙向有序鏈表的第一個(gè)節(jié)點(diǎn)連 接。
- 求二叉樹第K層的節(jié)點(diǎn)個(gè)數(shù)：
getNodeNumKthLevelRec, getNodeNumKthLevel
（1）如果二叉樹為空或者k<1返回0
（2）如果二叉樹不為空并且k==1捐祠，返回1
（3）如果二叉樹不為空且k>1碱鳞，返回左子樹中k-1層的子節(jié)點(diǎn)個(gè)數(shù)與右子樹k-1層子節(jié)點(diǎn)個(gè)數(shù)之和(這個(gè)描述有點(diǎn)奇怪)
private int GetNodeNumKthLevel(BinaryTreeNode Root, int k){
if(Root == NULL || k < 1) return 0;
if(k == 1) return 1;
int numLeft = GetNodeNumKthLevel(root.left, k-1);
int numRight = GetNodeNumKthLevel(root.right, k-1);
return (numLeft + numRight);
}
- 求二叉樹中葉子節(jié)點(diǎn)的個(gè)數(shù)：
（1）如果二叉樹為空，返回0
（2）如果二叉樹不為空且左右子樹為空踱蛀，返回1
（3）如果二叉樹不為空窿给，且左右子樹不同時(shí)為空崩泡，返回左子樹中葉子節(jié)點(diǎn)個(gè)數(shù)加上右子樹中葉子節(jié)點(diǎn)個(gè)數(shù) - 判斷兩棵二叉樹是否相同的樹：
（1）如果兩棵二叉樹都為空，返回真
（2）如果兩棵二叉樹一棵為空角撞，另一棵不為空，返回假
（3）如果兩棵二叉樹都不為空热康，如果對(duì)應(yīng)的左子樹和右子樹都同構(gòu)返回真，其他返回假 - 求二叉樹的鏡像（破壞和不破壞原來的樹兩種情況）：
（1）如果二叉樹為空褐隆，返回空
（2）如果二叉樹不為空剖踊，求左子樹和右子樹的鏡像，然后交換左子樹和右子樹
判斷兩個(gè)樹是否互相鏡像 - 求二叉樹中節(jié)點(diǎn)的最大距離：
（1）如果二叉樹為空衫贬，返回0德澈，同時(shí)記錄左子樹和右子樹的深度，都為0
（2）如果二叉樹不為空固惯，最大距離要么是左子樹中的最大距離梆造，要么是右子樹中的最大距離，要么是左子樹節(jié)點(diǎn)中到根節(jié)點(diǎn)的最大距離+右子樹節(jié)點(diǎn)中到根節(jié)點(diǎn)的最大距離葬毫，同時(shí)記錄左子樹和右子樹節(jié)點(diǎn)中到根節(jié)點(diǎn)的最大距離镇辉。 - 由前序遍歷序列和中序遍歷序列重建二叉樹：
rebuildBinaryTreeRec - 判斷二叉樹是不是完全二叉樹：
若設(shè)二叉樹的深度為h，除第 h 層外贴捡，其它各層 (1～h-1) 的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)忽肛，第 h 層所有的結(jié)點(diǎn)都連續(xù)集中在最左邊，這就是完全
二叉樹烂斋。
有如下算法屹逛，按層次（從上到下，從左到右）遍歷二叉樹汛骂，當(dāng)遇到一個(gè)節(jié)點(diǎn)的左子樹為空時(shí)罕模，則該節(jié)點(diǎn)右子樹必須為空，且后面遍歷的節(jié)點(diǎn)左
右子樹都必須為空帘瞭，否則不是完全二叉樹淑掌。
