剑指Offer（九）：变态跳台阶
public class Solution { public int JumpFloorII(int target) { if(target<=0){ return -1; }else if(target==1){ return 1; }else if(target==2){ return 2; }else{ return 2*JumpFloorII(target-1); } } }
剑指Offer（十）：矩形覆盖
public class Solution { public int RectCover(int target) { if(target<=0){ return 0; }else if(target==1){ return 1; }else if(target==2){ return 2; }else{ return RectCover(target-1)+RectCover(target-2); } } }
二叉搜索树
剑指Offer（二十三）：二叉搜索树的后序遍历序列
采用分治法的思想，找到根结点、左子树的序列、右子树的序列，分别判断左右子序列是否为二叉树的后序序列。
由题意可得：
后序遍历序列的最后一个元素为二叉树的根节点；
二叉搜索树左子树上所有的结点均小于根结点、右子树所有的结点均大于根结点。
算法步骤如下：
找到根结点；
遍历序列，找到第一个大于等于根结点的元素i，则i左侧为左子树、i右侧为右子树；
我们已经知道i左侧所有元素均小于根结点，那么再依次遍历右侧，看是否所有元素均大于根结点；若出现小于根结点的元素，则直接返回false；若右侧全都大于根结点，则：
分别递归判断左/右子序列是否为后序序列；
public class Solution { public boolean VerifySquenceOfBST(int [] sequence) { /首先对边界条件进行判断 if(sequence.length==0){ return false; } /但只有一个元素 if(sequence.length==1){ return true; } return ju(sequence,0,sequence.length-1); } public static boolean ju(int[] sequence,int low,int root){ ///递归的结束条件 if(low>=root){ return true; } int i=root; /首先从后往前找，小于root的值 while(i>low&&sequence[i-1]>sequence[root]){ i--; } ///然后循环判断是否有大于root的值不符合规范 for(int j=low;j<i;j++) if(sequence[j]>sequence[root]) return false; ///如果符合条件则递归进行 return ju(sequence,low,i-1)&&ju(sequence,i,root-1); } }
剑指Offer（二十六）：二叉搜索树与双向链表
//这个思路比较容易理解，中序遍历+ 双向链表。
//直接用中序遍历 public class Solution { TreeNode head = null; TreeNode tail = null; public TreeNode Convert(TreeNode pRootOfTree) { ConvertSub(pRootOfTree); return head; } private void ConvertSub(TreeNode pRootOfTree) { if(pRootOfTree==null) return; ConvertSub(pRootOfTree.left); if (tail == null) { tail = pRootOfTree; head = pRootOfTree; } else { tail.right = pRootOfTree; pRootOfTree.left = tail; tail = pRootOfTree; } ConvertSub(pRootOfTree.right); } }
剑指Offer（六十二）：二叉搜索树的第k个结点
核心思想：基于中序遍历
方法一：使用ArrayList将数据存储起来，之后将，取出前K-1个数据
import java.util.ArrayList; public class Solution { ArrayList<TreeNode> list=new ArrayList<TreeNode>(); TreeNode KthNode(TreeNode pRoot, int k) { if(pRoot==null) return null; InOrder(pRoot); if(k<=0) return null; if(list.size()<k) return null; TreeNode node=list.get(k-1); return node; } public void InOrder(TreeNode node){ if(node==null) return; InOrder(node.left); list.add(node); InOrder(node.right); } }
