Given two binary trees, write a function to check if they are the same or not. Two binary trees are considered the same if they are structurally identical and the nodes have the same value.
解法 判断二叉树是否相等，这个题目比较简单，用递归即可：
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public boolean isSameTree(TreeNode p, TreeNode q) { if (p == null && q == null) { return true; } else if (p == null || q == null) { return false; } else { return (p.val == q.val) && isSameTree(p.left, q.left) && isSameTree(p.right, q.right); } } }简化下代码：
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public boolean isSameTree(TreeNode p, TreeNode q) { if (p == null && q == null) return true; if (p == null || q == null) return false; return (p.val == q.val) && isSameTree(p.left, q.left) && isSameTree(p.right, q.right); } }[Description] Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
[Example] For example, this binary tree [1,2,2,3,4,4,3] is symmetric:
1 / \ 2 2 / \ / \ 3 4 4 3But the following [1,2,2,null,3,null,3] is not:
1 / \ 2 2 \ \ 3 3Note: Bonus points if you could solve it both recursively and iteratively.
[Answer]
/** * 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 isMirror(root, root); } public boolean isMirror(TreeNode t1, TreeNode t2) { if (t1 == null && t2 == null) return true; if (t1 == null || t2 == null) return false; return (t1.val == t2.val) && isMirror(t1.right, t2.left) && isMirror(t1.left, t2.right); } }给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。 示例： 二叉树：[3,9,20,null,null,15,7],
3 / \ 9 20 / \ 15 7返回其层次遍历结果：
[ [3], [9,20], [15,7] ] /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> lists = new ArrayList<>(); if (root != null) levelOrder(lists, root, 0); return lists; } void levelOrder(List<List<Integer>> lists, TreeNode root, int level) { List<Integer> list; if (lists == null || lists.size() < level + 1) list = new ArrayList<>(); else list = lists.get(level); list.add(root.val); if (lists.size() > level) lists.remove(level); lists.add(level, list); if (root.left != null) levelOrder(lists, root.left, level + 1); if (root.right != null) levelOrder(lists, root.right, level + 1); } }[Description] Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. Note: A leaf is a node with no children.
[Example] Given binary tree [3,9,20,null,null,15,7],
3 / \ 9 20 / \ 15 7return its depth = 3.
[Answer]
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public int maxDepth(TreeNode root) { if(root == null) return 0; if(root.left == null && root.right == null) return 1; int maxL = maxDepth(root.left); int maxR = maxDepth(root.right); if(maxL < maxR) return 1 + maxR; else return 1 + maxL; } }将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定有序数组: [-10,-3,0,5,9],
一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
0 / \ -3 9 / / -10 5 /** * 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) { TreeNode root; if (nums.length == 0) return null; if (nums.length == 1) root = new TreeNode(nums[0]); else { root = new TreeNode(nums.length / 2); root.val = nums[nums.length/2]; int[] left = new int[nums.length / 2]; int[] right = new int[nums.length - 1 - nums.length / 2]; for (int i = 0; i < nums.length; i++) { if (i < nums.length / 2) left[i] = nums[i]; else if (i > nums.length / 2) right[i - nums.length / 2 - 1] = nums[i]; } root.left = sortedArrayToBST(left); root.right = sortedArrayToBST(right); } return root; } }给定一个二叉树，判断它是否是高度平衡的二叉树。 本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public boolean isBalanced(TreeNode root) { if (root == null) return true; if (root.left == null && root.right == null) return true; return (Math.abs(maxDepth(root.left) - maxDepth(root.right)) < 2) && isBalanced(root.left) && isBalanced(root.right); } public int maxDepth(TreeNode root) { if (root == null) return 0; if (root.left == null && root.right == null) return 1; else return 1 + Math.max(maxDepth(root.left), maxDepth(root.right)); } }给定一个二叉树，找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public int minDepth(TreeNode root) { if (root == null) return 0; if (root.left == null && root.right == null) return 1; int min = Integer.MAX_VALUE; if (root.left != null) min = minDepth(root.left); if (root.right != null) min = Math.min(minDepth(root.right), min); return min + 1; } }给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
示例: 给定如下二叉树，以及目标和 sum = 22，
5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public boolean hasPathSum(TreeNode root, int sum) { if (root == null) return false; if (root.left == null && root.right == null) return sum == root.val; else return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val); } }给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。 在杨辉三角中，每个数是它左上方和右上方的数的和。
示例: 输入: 5 输出:
[ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ] class Solution { public List<List<Integer>> generate(int numRows) { List<List<Integer>> result = new ArrayList<List<Integer>>(numRows); if (numRows == 0) return result; List<Integer> listRow0 = new ArrayList<>(1); listRow0.add(1); result.add(listRow0); for (int i = 1; i < numRows; i++) { List<Integer> listRow = new ArrayList<>(i + 1); for (int j = 0; j < i + 1; j++) { if (j == 0 || j == i) listRow.add(1); else { listRow.add(result.get(i - 1).get(j - 1) + result.get(i - 1).get(j)); } } result.add(listRow); } return result; } }给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。 在杨辉三角中，每个数是它左上方和右上方的数的和。
示例: 输入: 3 输出: [1,3,3,1]
进阶： 你可以优化你的算法到 O(k) 空间复杂度吗？
class Solution { // 119. 杨辉三角 II public List<Integer> getRow(int rowIndex) { if (rowIndex == 0) { List<Integer> list0 = new ArrayList<>(1); list0.add(1); return list0; } else { List<Integer> res = new ArrayList<>(rowIndex + 1); List<Integer> listPrev = getRow(rowIndex-1); for (int i = 0; i < rowIndex + 1; i++) { if (i == 0 || i == rowIndex) res.add(1); else { res.add(listPrev.get(i - 1) + listPrev.get(i)); } } return res; } } }给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
注意：你不能在买入股票前卖出股票。
示例 1: 输入: [7,1,5,3,6,4] 输出: 5 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2: 输入: [7,6,4,3,1] 输出: 0 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
class Solution { public int maxProfit(int[] prices) { int minPrice = Integer.MAX_VALUE; int maxProfit = 0; for (int i = 0; i < prices.length; i++) { int nowPrice = prices[i]; if (nowPrice < minPrice) minPrice = nowPrice; else { maxProfit = Math.max(maxProfit, nowPrice - minPrice); } } return maxProfit; } }给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。 说明：本题中，我们将空字符串定义为有效的回文串。
示例 1: 输入: “A man, a plan, a canal: Panama” 输出: true
示例 2: 输入: “race a car” 输出: false
class Solution { public boolean isPalindrome(String s) { s = s.toLowerCase().replaceAll("[^a-z^A-Z^0-9]", ""); if (s.length() == 0) return true; else { char[] strs = s.toCharArray(); for (int i = 0; i < strs.length / 2; i++) { if (strs[i] != strs[strs.length - 1 - i]) return false; } } return true; } }[Description] Given a non-empty array of integers, every element appears twice except for one. Find that single one. Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
[Example] Example 1: Input: [2,2,1] Output: 1
Example 2: Input: [4,1,2,1,2] Output: 4
[Answer]
// Runtime: 88 ms, faster than 5.02% of Java online submissions for Single Number. // Memory Usage: 39 MB, less than 76.72% of Java online submissions for Single Number. class Solution { public int singleNumber(int[] nums) { int size = nums.length; if(size == 0) return 0; if(size < 2) return nums[0]; ArrayList<Integer> list = new ArrayList(); for (int i = 0; i < size; i++) { int index = list.indexOf(nums[i]); if (index >= 0) list.remove(index); else list.add(nums[i]); } return list.get(0); } } // Runtime: 7 ms, faster than 32.69% of Java online submissions for Single Number. // Memory Usage: 39.2 MB, less than 73.94% of Java online submissions for Single Number. class Solution { public int singleNumber(int[] nums) { Set<Integer> set = new HashSet<>(); for(int i = 0; i < nums.length; i++) { if(!set.contains(nums[i])) set.add(nums[i]); else set.remove(nums[i]); } return set.iterator().next(); } }给定一个链表，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true 。 否则，返回 false 。
进阶： 你能用 O(1)（即，常量）内存解决此问题吗？
/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public boolean hasCycle(ListNode head) { if (head == null || head.next == null) return false; ListNode slow = head; ListNode fast = head.next; while (slow != fast) { if (fast.next == null || fast.next.next == null) return false; fast = fast.next.next; slow = slow.next; } return true; } }给定一个字符串，逐个翻转字符串中的每个单词。
说明： 无空格字符构成一个 单词 。 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
示例 1： 输入：“the sky is blue” 输出：“blue is sky the”
示例 2： 输入：" hello world! " 输出：“world! hello” 解释：输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
示例 3： 输入：“a good example” 输出：“example good a” 解释：如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
示例 4： 输入：s = " Bob Loves Alice " 输出：“Alice Loves Bob”
示例 5： 输入：s = “Alice does not even like bob” 输出：“bob like even not does Alice”
提示： 1 <= s.length <= 104 s 包含英文大小写字母、数字和空格 ’ ’ s 中 至少存在一个 单词
进阶： 请尝试使用 O(1) 额外空间复杂度的原地解法。
class Solution { public String reverseWords(String s) { String res = ""; String word = ""; int index = 0; boolean start = false; char[] chars = s.toCharArray(); while (index < chars.length) { if (chars[index] == ' ') { if (start) { if (res.equals("") || res.trim().length() == 0) res = word; else res = word + " " + res; start = false; word = ""; } } else { start = true; word += chars[index]; } index++; } if (!word.equals("")){ if (res.equals("") || res.trim().length() == 0) res = word; else res = word + " " + res; } return res; } }假设按照升序排序的数组在预先未知的某个点上进行了旋转。例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] 。 请找出其中最小的元素。
示例 1： 输入：nums = [3,4,5,1,2] 输出：1
示例 2： 输入：nums = [4,5,6,7,0,1,2] 输出：0
示例 3： 输入：nums = [1] 输出：1
提示： 1 <= nums.length <= 5000 -5000 <= nums[i] <= 5000 nums 中的所有整数都是 唯一 的 nums 原来是一个升序排序的数组，但在预先未知的某个点上进行了旋转
class Solution { public int findMin(int[] nums) { for (int i = nums.length - 1; i > 0; i--) { if (nums[i] < nums[i - 1]) return nums[i]; } return nums[0]; } }假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 请找出其中最小的元素。
注意数组中可能存在重复的元素。
示例 1： 输入: [1,3,5] 输出: 1
示例 2： 输入: [2,2,2,0,1] 输出: 0
说明： 这道题是 寻找旋转排序数组中的最小值 的延伸题目。 允许重复会影响算法的时间复杂度吗？会如何影响，为什么？
class Solution { public int findMin(int[] nums) { for (int i = nums.length - 1; i > 0; i--) { if (nums[i] < nums[i - 1]) return nums[i]; } return nums[0]; } }设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
push(x) —— 将元素 x 推入栈中。 pop() —— 删除栈顶的元素。 top() —— 获取栈顶元素。 getMin() —— 检索栈中的最小元素。
class MinStack { /** * initialize your data structure here. */ List<Integer> listData; List<Integer> listMin; public MinStack() { listData = new LinkedList<>(); listMin = new LinkedList<>(); } public void push(int x) { listData.add(x); if (listMin.size() > 0) listMin.add(Math.min(x, getMin())); else listMin.add(x); } public void pop() { listData.remove(listData.size() - 1); listMin.remove(listMin.size() - 1); } public int top() { return listData.get(listData.size() - 1); } public int getMin() { return listMin.get(listMin.size() - 1); } } /** * Your MinStack object will be instantiated and called as such: * MinStack obj = new MinStack(); * obj.push(x); * obj.pop(); * int param_3 = obj.top(); * int param_4 = obj.getMin(); */编写一个程序，找到两个单链表相交的起始节点。
注意： 如果两个链表没有交点，返回 null. 在返回结果后，两个链表仍须保持原有的结构。 可假定整个链表结构中没有循环。 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode pA = headA, pB = headB; while(pA != pB) { pA = (pA == null ? headB : pA.next); pB = (pB == null ? headA : pB.next); } return pA; } }给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。 函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。
说明: 返回的下标值（index1 和 index2）不是从零开始的。 你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
示例: 输入: numbers = [2, 7, 11, 15], target = 9 输出: [1,2] 解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
class Solution { public int[] twoSum(int[] numbers, int target) { int indexA = 0, indexB = 0; for (int i = 0; i < numbers.length; i++) { for (int j = i + 1; j < numbers.length; j++) { if (numbers[i] + numbers[j] == target) { indexA = i; indexB = j; break; } else if (numbers[i] + numbers[j] > target) break; } } return new int[]{indexA + 1, indexB + 1}; } }你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
class Solution { public int rob(int[] nums) { if (nums == null || nums.length == 0) return 0; int length = nums.length; if (length == 1) return nums[0]; int first = nums[0]; int second = Math.max(nums[0], nums[1]); for (int i = 2; i < length; i++) { int temp = second; second = Math.max(first + nums[i], second); first = temp; } return second; } }