思路是这样的：在二叉树的前序遍历序列中，第一个数字总是树的根节点的值，但在中序遍历序列中，根节点的值保存在序列的中间，左子树的节点的值位于根节点的值的左边，而右子树则相反，然后既然找到了左右子树我们又可以使用同样的方法在前序和中序中分别构建左右子树，这样我们就能够使用递归的方法完成；（上面算法中的ps、is、ie分别表示前序的开始位置，中序的开始位置和中序的结束位置；）
113. 路径总和 II（剑指Offer面试题34）
参考答案：（3ms）
public List<List<Integer>> pathSum(TreeNode root, int sum) { List<Integer> nodeList = new ArrayList<Integer>(); List<List<Integer>> sumList = new ArrayList<List<Integer>>(); if (root == null) { return sumList; } pathSum2(root, sum, sumList, nodeList); return sumList; } public void pathSum2(TreeNode root, int target, List<List<Integer>> sumList, List<Integer> nodeList) { if (root.left == null && root.right == null) { nodeList.add(root.val); int sum = 0; for (Integer integer : nodeList) { sum += integer; } if (sum == target) { sumList.add(new ArrayList<Integer>(nodeList)); } return; } nodeList.add(root.val); if (root.left != null) { pathSum2(root.left, target, sumList, nodeList); nodeList.remove(nodeList.size() - 1); } if (root.right != null) { pathSum2(root.right, target, sumList, nodeList); nodeList.remove(nodeList.size() - 1); } } 230. 二叉搜索树中第K小的元素（类似剑指Offer面试题54）
我的答案：（23ms）
public int kthSmallest(TreeNode root, int k) { // 正确性判断 if (null == root || k < 1) { return -1; } List<Integer> result = preOrder(root); // 从小到大排序 Collections.sort(result); return result.get(k - 1); } /** * 遍历整棵树并返回一个List * * @param root * @return */ private List<Integer> preOrder(TreeNode root) { List result = new ArrayList(); if (null != root) { result.add(root.val); result.addAll(preOrder(root.left)); result.addAll(preOrder(root.right)); } return result; }贼蠢，完全没有用到二叉搜索树的特性
参考答案：（1ms）
public int kthSmallest(TreeNode root, int k) { int count = countNodes(root.left); if (k <= count) { return kthSmallest(root.left, k); } else if (k > count + 1) { return kthSmallest(root.right, k - 1 - count); } return root.val; } public int countNodes(TreeNode n) { if (n == null) return 0; return 1 + countNodes(n.left) + countNodes(n.right); } 449. 序列化二叉搜索树（类似剑指Offer面试题37）
参考答案：（12ms）
// Encodes a tree to a single string. public String serialize(TreeNode root) { StringBuffer sb = new StringBuffer(); preOrder(root,sb); return sb.toString(); } private static void preOrder(TreeNode root, StringBuffer sb){ if(root==null) return; sb.append(root.val).append('#'); preOrder(root.left,sb); preOrder(root.right,sb); } // Decodes your encoded data to tree. public TreeNode deserialize(String data) { if(data==null) return null; int val =0; TreeNode root = null; for(int i=0;i<data.length();i++){ if(data.charAt(i)!='#'){ val = val*10+(data.charAt(i)-'0'); }else{ root = insert(root,val); val=0; } } return root; } private static TreeNode insert(TreeNode root,int val){ if(root==null) return new TreeNode(val); if(root.val<val) root.right = insert(root.right,val); else root.left = insert(root.left,val); return root; } 572. 另一个树的子树（类似剑指Offer面试题26）
参考答案：（15ms）
public boolean isSubtree(TreeNode s, TreeNode t) { // Write your code here if (s == null) { return t == null; } if (s.val == t.val && isSametree(s, t)) { return true; } return isSubtree(s.left, t) | isSubtree(s.right, t); } private boolean isSametree(TreeNode s, TreeNode t) { if (s == null) { return t == null; } if (t == null) { return false; } if (s.val != t.val) { return false; } return isSametree(s.left, t.left) & isSametree(s.right, t.right); }我的第一个反应还是去把两棵树的前序遍历的数组弄出来然后判断是否为子集，但是树这样的天然递归结构这样写很自然...
简单总结