剑指offer-2~4

2.替换空格
请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

public class Solution {
    public String replaceSpace(StringBuffer str) {
        for(int i=0;i<str.length();i++){
            if(str.charAt(i)==' '){
                str.deleteCharAt(i);
                str.insert(i,"%20");
            }    
        }
        return str.toString();
    }
}

public class Solution {
    public String replaceSpace(StringBuffer str) {
        StringBuilder sb = new StringBuilder();
        int j = 0;
        int i = 0;
        for(;i<str.length();i++){
            if(str.charAt(i)==' '){
                if(j!=i){
                    sb.append(str.subSequence(j, i));
                    sb.append("%20");
                }else{
                    sb.append("%20");
                }
                j=i+1;
            }
        }
        if(j != i){
            sb.append(str.subSequence(j,str.length()));
        }
        return sb.toString();
    }
}

3.从尾到头打印链表
输入一个链表，从尾到头打印链表每个节点的值。

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        if(listNode == null){
            return res;
        }
        ArrayList<ListNode> listNodes = new ArrayList<ListNode>();
        listNodes.add(listNode);
        while(listNode.next!=null){
                listNode = listNode.next;
                listNodes.add(listNode);
        }
        
        for(int i= listNodes.size()-1;i>=0;i--){
            int item = listNodes.get(i).val;
            res.add(item);
        }
        return res;
    }
}

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        if(listNode ==null){
            return list;
        }
        while(listNode!=null){
            list.add(0,listNode.val);
            listNode = listNode.next;
        }
        return list;
    }
}

4.重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if(pre.length==0){
            return null;
        }
        return build(pre,in,0,0,pre.length);
    }
    
    public TreeNode build(int[] pre,int[] in,int preStart,int inStart,int size){
        if(size==0){
            return null;
        }
        int nodeVal = pre[preStart];
        TreeNode treeNode = new TreeNode(nodeVal);
        
        int leftSize = 0;
        int rightInStart = inStart;
        for(;leftSize < size;leftSize++,rightInStart++){
            if( in[rightInStart] == nodeVal ){
                rightInStart++;
                break;
            }
        }
        int rightSize = size - leftSize - 1;
            
        treeNode.left  = build( pre , in , preStart + 1 , inStart , leftSize);
        treeNode.right = build( pre , in , preStart + leftSize+1,rightInStart,rightSize);
        return treeNode;
    }
}