将字符串中空格变成%20

思路：
计算新数组大小，2*空格的个数
建立两个指针，一个指向原数组的尾部位置，一个指向新数组的尾部。
将i从后往前遍历，并把字符复制到j所在位置，直到遇到空格，j向前移动3格，填入%20

Java

public class Solution {
    public String replaceSpace(StringBuffer str) {
        if (str == null) {
            return null;
        }
        int count = 0;
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == ' ') {
                count++;
            }
        }
        int len = str.length() - 1;
        int newLen  = len + count * 2;
        str.setLength(newLen + 1);
 
        while (len >= 0 && len < newLen) {
            if (str.charAt(len) != ' ') {
                str.setCharAt(newLen, str.charAt(len));
                newLen--;
            } else {
                str.setCharAt(newLen--, '0');                
                str.setCharAt(newLen--, '2');
                str.setCharAt(newLen--, '%');
            }
            len--;
        }
        return str.toString();
    }
}

从尾到头打印链表

思路1
将链表放入栈中，再弹出
思路2
递归

Java

/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
public class Solution {
    private ArrayList<Integer> arrayList = new ArrayList<>();
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
      if (listNode != null) {
        printListFromTailToHead(listNode.next);
        arrayList.add(listNode.val);
        
      }
      return arrayList;
    }
}

重建二叉树

输入二叉树的前序遍历和中序遍历的结果，重建此二叉树
思路
前序遍历的第一个节点为根节点，中序遍历的根节点的左边是左子树的节点，右边是右子树的节点

1 2 4 7 3 5 6 8
4 7 2 1 5 3 8 6
1是根结点，4 7 2、2 4 7是左子树，5 3 8 6、3 5 6 8是右子树

4 7 2是中序遍历，2 4 7是前序遍历
2是根结点，4 7是左子树，如此，将新子树作为树。

Java

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
      return constructTree(pre, in, 0, pre.length-1, 0, in.length-1);
    }
    public TreeNode constructTree(int[] preTree, int[] inTree, int pHead, int pEnd, int iHead, int iEnd) {
      TreeNode node = new TreeNode(preTree[pHead]);  // 前序遍历根结点
      if (pHead == pEnd && iHead == iEnd) {
        return node;
      }
      // 找出中序遍历的根结点
      int iRoot=0;
      for (iRoot=iHead; iRoot<inTree.length; iRoot++) {
        if (inTree[iRoot] == preTree[pHead]) break;
      }
      int leftDepth = iRoot - iHead;
      int rightDepth = iEnd - iRoot;
      if (leftDepth > 0)
        node.left = constructTree(preTree, inTree, pHead + 1, pHead + leftDepth, iHead, iRoot - 1);
      if ( rightDepth > 0)
        node.right = constructTree(preTree, inTree, pHead + leftDepth + 1, pEnd, iRoot + 1, iEnd);
      return node;
    }
}