记下自己遇到的难点与值得思考的地方
给定一个二叉树，判断其是否是一个有效的二叉搜索树。 假设一个二叉搜索树具有如下特征： 节点的左子树只包含小于当前节点的数。 节点的右子树只包含大于当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。
采用递归 —— 一个结点一个结点的判断 。 为每一个结点值 val给定上界 lower和下界 upper，即每次递归应满足
lower < val && val > upper
否则，返回 false。 应注意：当 node为 null时，为 true。
要解决这道题首先我们要了解二叉搜索树有什么性质可以给我们利用，由题目给出的信息我们可以知道：如果该二叉树的左子树不为空，则左子树上所有节点的值均小于它的根节点的值； 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；它的左右子树也为二叉搜索树。 这启示我们设计一个递归函数 helper(root, lower, upper) 来递归判断，函数表示考虑以 root 为根的子树，判断子树中所有节点的值是否都在 (l,r)(l,r) 的范围内（注意是开区间）。如果 root 节点的值 val 不在 (l,r)(l,r) 的范围内说明不满足条件直接返回，否则我们要继续递归调用检查它的左右子树是否满足，如果都满足才说明这是一棵二叉搜索树。 那么根据二叉搜索树的性质，在递归调用左子树时，我们需要把上界 upper 改为 root.val，即调用 helper(root.left, lower, root.val)，因为左子树里所有节点的值均小于它的根节点的值。同理递归调用右子树时，我们需要把下界 lower 改为 root.val，即调用 helper(root.right, root.val, upper)。 函数递归调用的入口为 helper(root, -inf, +inf)， inf 表示一个无穷大的值。
/** * 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) { return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE); } public boolean isValidBST(TreeNode node, long lower, long upper) { if(node == null) return true; long val = node.val; if(lower >= val || val >= upper) return false; return isValidBST(node.left, lower, val) && isValidBST(node.right, val, upper); } }给定一个二叉树，检查它是否是镜像对称的。
leetcode 解析
使用两个指针 p, q分别指向该二叉树。 判断过程二叉树是否为对称二叉树就转换为：
每次递归，p 向左移，q 向右移，判断 p、q 当前指向的节点值是否相等； 递归基例为：p、q 当前指向的节点是否为空的情况；p、q 当前指向的节点值是否相等的情况
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public boolean isSymmetric(TreeNode root) { return isSymmetric(root, root); } public boolean isSymmetric(TreeNode p, TreeNode q) { if(p == null && q == null) return true; if(p == null || q == null) return false; return p.val == q.val && isSymmetric(p.left, q.right) && isSymmetric(p.right, q.left); } }对该二叉树进行两次 “先序遍历”，将遍历结果存放在字符串中：
第一次：root ，root.left，root.right 第二次：root,，root.right，root.left
然后，根据两个字符串是否相等，返回结果。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public boolean isSymmetric(TreeNode root) { StringBuilder sbLeft=new StringBuilder(); StringBuilder sbRight=new StringBuilder(); go(root,sbLeft,true); go(root,sbRight,false); return sbLeft.toString().equals(sbRight.toString()); } private void go(TreeNode node,StringBuilder sb,boolean isLeft){ if (node!=null){ sb.append(node.val).append("#"); if (isLeft){ go(node.left,sb,isLeft); go(node.right,sb,isLeft); }else{ go(node.right,sb,isLeft); go(node.left,sb,isLeft); } }else{ sb.append("#"); } } }将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。 本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
对一个二叉搜索树进行中序遍历可以得到一个有序列表。 我们将这个过程反过来，构建一个二叉搜索树：
对于数组的 nums[left] ~ nums[right] 这一部分，取中间的 nums[(left + right) / 2] 作为根节点； 然后，对它进行 nums[left] ~ nums[(left + right) / 2 - 1] 、 nums[(left + right) / 2 + 1] ~ nums[right] 分别再按上述方法进行。 基例为 left > rigth
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public TreeNode sortedArrayToBST(int[] nums) { if(nums.length == 0) return null; int mid = nums.length / 2; TreeNode root = new TreeNode(nums[mid]); sortedArrayToBST(nums, root, true, 0, mid - 1); sortedArrayToBST(nums, root, false, mid + 1 , nums.length - 1); return root; } public void sortedArrayToBST(int[] nums, TreeNode root, boolean isLeft, int left, int right) { if(left > right) return; int mid = (left + right) / 2; TreeNode node = new TreeNode(nums[mid]); if(isLeft) { root.left = node; sortedArrayToBST(nums, node, true, left, mid - 1); sortedArrayToBST(nums, node, false, mid + 1, right); } else { root.right = node; sortedArrayToBST(nums, node, true, left, mid - 1); sortedArrayToBST(nums, node, false, mid + 1, right); } } }