92. Reverse Linked List II
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
ListNode dummy = new ListNode(-999);
dummy.next = head;
ListNode cur = dummy;
int index = 1;
while(index<m){
index++;
cur = cur.next;
}
ListNode p = cur.next;
if(p.next == null)
return dummy.next;
ListNode q = p.next;
index ++;
while(index <= n){
p.next = q.next;
q.next = cur.next;
cur.next = q;
q = p.next;
index++;
}
return dummy.next;
}
}
93. Restore IP Addresses
回溯法：
class Solution {
public List<String> restoreIpAddresses(String s) {
List<String> res = new ArrayList<String>();
if(s==null || s.length()==0 || s.length()>12)
return res;
backtracking(s,res,"",0,0);
return res;
}
public static void backtracking(String s,List<String> res,String ss,int start,int count){
if(count==4 && start == s.length()){
String a = ss.substring(0,ss.length()-1);
res.add(a);
}
for(int i=start;i<start+3 && i<s.length();i++){
if(i>start && s.substring(start,start+1).equals("0"))
break;
if(Integer.parseInt(s.substring(start,i+1)) <= 255){
backtracking(s,res,ss+s.substring(start,i+1)+".",i+1,count+1);
}
}
}
}
94. Binary Tree Inorder Traversal
二叉树的中序遍历非递归思路
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if(root == null)
return res;
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode t = root;
while(t!=null){
stack.push(t);
t = t.left;
}
while(!stack.empty()){
t = stack.pop();
res.add(t.val);
t = t.right;
while(t!=null){
stack.push(t);
t = t.left;
}
}
return res;
}
}
95. Unique Binary Search Trees II
这题是 96 Unique Binary Search Trees 的延展，它已经不是让求不同构二叉树的种数，而是直接给出这些不同构的二叉树。
1. 每一次都在一个范围内随机选取一个结点作为根。
2. 每选取一个结点作为根，就把树切分成左右两个子树，直至该结点左右子树为空。
大致思路如上，可以看出这也是一个可以划分成子问题求解的题目，所以考点是动态规划。
但具体对于本题来说，采取的是自底向上的求解过程。
1. 选出根结点后应该先分别求解该根的左右子树集合，也就是根的左子树有若干种，它们组成左子树集合，根的右子树有若干种，它们组成右子树集合。
2. 然后将左右子树相互配对，每一个左子树都与所有右子树匹配，每一个右子树都与所有的左子树匹配。然后将两个子树插在根结点上。
3. 最后，把根结点放入链表中。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<TreeNode> generateTrees(int n) {
if(n<=0)
return new ArrayList<TreeNode>();
return generateHelper(1,n);
}
public static List<TreeNode> generateHelper(int start,int end){
List<TreeNode> res = new ArrayList<TreeNode>();
if(start>end){
res.add(null);
return res;
}
for(int i=start;i<=end;i++){
List<TreeNode> leftNode = generateHelper(start,i-1);
List<TreeNode> rightNode = generateHelper(i+1,end);
for(int left=0;left<leftNode.size();left++)
for(int right=0;right<rightNode.size();right++){
TreeNode t = new TreeNode(i);
t.left = leftNode.get(left);
t.right = rightNode.get(right);
res.add(t);
}
}
return res;
}
}
96. Unique Binary Search Trees
这 道题要求可行的二叉查找树的数量，其实二叉查找树可以任意取根，只要满足中序遍历有序的要求就可以。从处理子问题的角度来看，选取一个结点为根，就把结点 切成左右子树，以这个结点为根的可行二叉树数量就是左右子树可行二叉树数量的乘积，所以总的数量是将以所有结点为根的可行结果累加起来。写成表达式如下：
class Solution {
public int numTrees(int n) {
int [] G = new int[n+1];
G[0] = G[1] = 1;
for(int i=2; i<=n; ++i) {
for(int j=1; j<=i; ++j) {
G[i] += G[j-1] * G[i-j];
}
}
return G[n];
}
}
97. Interleaving String
我自己的思路：回溯法，不过超时了，记录下：
class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
if(s3.length() != s2.length() + s1.length())
return false;
return backtracking(s1,s2,s3,0,0);
}
public boolean backtracking(String s1,String s2,String s3,int start1,int start2){
if(start1 == s1.length() && start2 == s2.length())
return true;
if((start1<s1.length() && s1.charAt(start1) != s3.charAt(start1+start2)) && (start2<s2.length() && s2.charAt(start2) != s3.charAt(start1+start2)))
return false;
return (start1 < s1.length() && s1.charAt(start1) == s3.charAt(start1 + start2) && backtracking(s1,s2,s3,start1+1,start2)) || (start2 < s2.length() && s2.charAt(start2) == s3.charAt(start1 + start2) && backtracking(s1,s2,s3,start1,start2+1));
}
}
因此考虑用动态规划做。
s1, s2只有两个字符串，因此可以展平为一个二维地图，判断是否能从左上角走到右下角。
当s1到达第i个元素，s2到达第j个元素:
地图上往右一步就是s2[j-1]匹配s3[i+j-1]。
地图上往下一步就是s1[i-1]匹配s3[i+j-1]。
示例：s1="aa",s2="ab",s3="aaba"。标1的为可行。最终返回右下角。
class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
if(s1.length() + s2.length() != s3.length())
return false;
boolean[][] arr = new boolean[s1.length()+1][s2.length()+1];
arr[0][0] = true;
for(int i=1;i<s2.length()+1;i++){
if(arr[0][i-1] && s2.charAt(i-1)==s3.charAt(i-1))
arr[0][i] = true;
else
arr[0][i] = false;
}
for(int j=1;j<s1.length()+1;j++){
if(arr[j-1][0] && s1.charAt(j-1) == s3.charAt(j-1))
arr[j][0] = true;
else
arr[j][0] = false;
}
for(int j=1;j<s1.length()+1;j++)
for(int i=1;i<s2.length()+1;i++){
if((arr[j-1][i] && s1.charAt(j-1)==s3.charAt(i+j-1)) || (arr[j][i-1] && s2.charAt(i-1)==s3.charAt(i+j-1)))
arr[j][i] = true;
else
arr[j][i] = false;
}
return arr[s1.length()][s2.length()];
}
}
98. Validate Binary Search Tree
按照中序遍历的思路，如果发现遍历的下一个节点比前一个节点大，那么继续遍历，如果比前一个节点小，则返回false。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isValidBST(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if(root == null)
return true;
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode t = root;
while(t!=null){
stack.push(t);
t = t.left;
}
while(!stack.empty()){
t = stack.pop();
if(res.size()>0 && t.val <= res.get(res.size()-1))
return false;
res.add(t.val);
t = t.right;
while(t!=null){
stack.push(t);
t = t.left;
}
}
return true;
}
}
99. Recover Binary Search Tree
二叉排序树中有两个节点被交换了，要求把树恢复成二叉排序树。
最简单的办法，中序遍历二叉树生成序列，然后对序列中排序错误的进行调整。最后再进行一次赋值操作。
但这种方法要求n的空间复杂度，题目中要求空间复杂度为常数，所以需要换一种方法。
递归中序遍历二叉树，设置一个pre指针，记录当前节点中序遍历时的前节点，如果当前节点大于pre节点的值，说明需要调整次序。
有一个技巧是如果遍历整个序列过程中只出现了一次次序错误，说明就是这两个相邻节点需要被交换。如果出现了两次次序错误，那就需要交换这两个节点。
我们交换的是两个节点的值。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
TreeNode mistake1,mistake2;
TreeNode pre;
public void recursive_traversal(TreeNode root){
if(root==null)
return;
recursive_traversal(root.left);
if(pre!=null && root.val<pre.val){
if(mistake1==null){
mistake1 = pre;
mistake2 = root;
}
else
mistake2 = root;
}
pre = root;
recursive_traversal(root.right);
}
public void recoverTree(TreeNode root) {
recursive_traversal(root);
int temp = mistake1.val;
mistake1.val = mistake2.val;
mistake2.val = temp;
}
}
100. Same Tree
递归
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p==null && q==null)
return true;
else if(p==null || q== null)
return false;
else if(p.val != q.val)
return false;
return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
}
}
