我的答案：（53ms）
private static int INT_MIN = Integer.MIN_VALUE; private static int INT_MAX = Integer.MAX_VALUE; public boolean isValidBST(TreeNode root) { // 如果节点为空则满足二叉搜索树条件 if (null == root) { return true; } // 如果左孩子结点大于了根节点则返回false if (null != root.left && findMax(root.left) > root.val) { return false; } // 如果右孩子结点小于了根节点则返回false if (null != root.right && findMin(root.right) < root.val) { return false; } // 递归判断左子树和右子树，若其中有一颗不是BST树，则返回false if (!isValidBST(root.left) || !isValidBST(root.right)) { return false; } // 通过所有判断则是一颗BST树 return true; } /** * 找到一颗非空树中的最大值 * * @param root * @return */ private int findMax(TreeNode root) { int maxVal = INT_MIN; int leftMaxVal = INT_MIN; int rightMaxVal = INT_MIN; if (null != root) { // 最大值默认等于当前节点值 maxVal = root.val; leftMaxVal = findMax(root.left); rightMaxVal = findMax(root.right); // maxVal等于当前maxVal与leftMaxVal中较大的一个 maxVal = maxVal > leftMaxVal ? maxVal : leftMaxVal; // maxVal等于当前maxVal与rightMaxVal中较大的一个 maxVal = maxVal > rightMaxVal ? maxVal : rightMaxVal; } return maxVal; } /** * 找到一颗非空树的最小值 * * @param root * @return */ private int findMin(TreeNode root) { int minVal = INT_MAX; int leftMinVal = INT_MAX; int rightMinVal = INT_MAX; if (null != root) { // 最小值默认为当前节点值 minVal = root.val; leftMinVal = findMin(root.left); rightMinVal = findMin(root.right); // minVal等于当前minVal与leftMinVal中较小的一个 minVal = minVal < leftMinVal ? minVal : leftMinVal; // minVal等于当前minVal与rightMinVal中较小的一个 minVal = minVal < rightMinVal ? minVal : rightMinVal; } return minVal; }自己写的时候提交错了很多次..没有掌握到二分搜索树的精髓..
参考答案：（2ms）
public boolean isValidBST(TreeNode root) { if (root == null) return true; return valid(root, Long.MIN_VALUE, Long.MAX_VALUE); } public boolean valid(TreeNode root, long low, long high) { if (root == null) return true; if (root.val <= low || root.val >= high) return false; return valid(root.left, low, root.val) && valid(root.right, root.val, high); }这答案写得我服了..真服..
101. 对称二叉树（剑指Offer面试题28）
参考答案：（12ms）
public boolean isSymmetric(TreeNode root) { return isSymmetric(root, root); } public boolean isSymmetric(TreeNode root1, TreeNode root2) { if (null == root1 && null == root2) { return true; } if (null == root1 || null == root2) { return false; } if (root1.val != root2.val) { return false; } return isSymmetric(root1.left, root2.right) && isSymmetric(root1.right, root2.left); }自己做的思路是使用中序遍历来判断（转成数组之后是对称的），但是出了很多问题，就是需要考虑null值，中序遍历中并不能很好地把一棵树保存为一个完整二叉树的样子..所以看了下参考答案..写得服..
104. 二叉树的最大深度（剑指Offer面试题55）
我的答案：（3ms）
public int maxDepth(TreeNode root) { int leftHeight, rightHeight; if (null == root) { return 0; } else { // 计算每个子树的高度 leftHeight = maxDepth(root.left); rightHeight = maxDepth(root.right); return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1; } }参考答案：（0ms）
public int maxDepth(TreeNode root) { if(root==null) return 0; return Math.max(maxDepth(root.left)+1,maxDepth(root.right)+1); } 105. 从前序与中序遍历序列构造二叉树（剑指Offer面试题7）
参考答案：（2ms）
public TreeNode buildTree(int[] preorder, int[] inorder) { if (preorder == null || preorder.length == 0) { return null; } return buildTree(preorder, inorder, 0, 0, inorder.length - 1); } private TreeNode buildTree(int[] preorder, int[] inorder, int ps, int is, int ie) { int val = preorder[ps]; TreeNode node = new TreeNode(val); int iRoot = ie; while (iRoot > is) { if (val == inorder[iRoot]) { break; } iRoot--; } if (iRoot > is) { node.left = buildTree(preorder, inorder, ps + 1, is, iRoot - 1); } if (iRoot < ie) { node.right = buildTree(preorder, inorder, ps + 1 + (iRoot - is), iRoot + 1, ie); } return node; }