题目描述 颠倒给定的 32 位无符号整数的二进制位。 示例 1： 输入: 00000010100101000001111010011100 输出: 00111001011110000010100101000000 解释: 输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596， 因此返回 964176192，其二进制表示形式为 00111001011110000010100101000000。 示例 2： 输入：11111111111111111111111111111101 输出：10111111111111111111111111111111 解释：输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293， 因此返回 3221225471 其二进制表示形式为 10111111111111111111111111111111 。 解法 JDK实现 public int reverseBits(int n) { return Inte....
题目描述 给你一个整数数组 arr，请你帮忙统计数组中每个数的出现次数。 如果每个数的出现次数都是独一无二的，就返回 true；否则返回 false。 示例 1： 输入：arr = [1,2,2,1,1,3] 输出：true 解释：在该数组中，1 出现了 3 次，2 出现了 2 次，3 只出现了 1 次。没有两个数的出现次数相同。 示例 2： 输入：arr = [1,2] 输出：false 示例 3： 输入：arr = [-3,0,1,-3,1,1,1,-3,10,0] 输出：true 解法 使用哈希表解决，第一遍存储每个数字出现的次数，第二遍存储用set存储出现的次数，如果set插入重复，即不是独一无二的出现次数 public boolean uniqueOccurrences(int[] arr) { Map<Integer, Integer> arrCountMap = new HashMap<>(); for(int i = 0; i < arr.length; i++) { arrCountMap.put(ar....
题目描述 给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。 示例 1: 输入: [3,2,3] 输出: 3 示例 2: 输入: [2,2,1,1,1,2,2] 输出: 2 解法 摩尔投票法 思路： 候选人(cand_num)初始化为nums[0]，票数count初始化为1。 当遇到与cand_num相同的数，则票数count = count + 1，否则票数count = count - 1。 当票数count为0时，更换候选人，并将票数count重置为1。 遍历完数组后，cand_num即为最终答案。 go代码如下： func majorityElement(nums []int) int { /** * 摩尔投票法 */ var count = 1 var base = nums[0] for i:=1; i<len(nums); i++ { if base == nums[i] { count += 1 ....
题目 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。 说明： 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？ 示例 1: 输入: [2,2,1] 输出: 1 示例 2: 输入: [4,1,2,1,2] 输出: 4 解法 1.哈希表 这种方式大家都能想到，比较简单。不过需要额外的空间复杂度，就不写代码了。 2.位运算-异或 异或的逻辑是相同为0， 不同为1，相同两个数经过两次异或运算都是0. go代码如下： func singleNumber(nums []int) int { result := 0 for _, v := range nums { result ^= v } return result } 运行结果如下：
题目描述 给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为 2 或 0。如果一个节点有两个子节点的话，那么该节点的值等于两个子节点中较小的一个。 更正式地说，root.val = min(root.left.val, root.right.val) 总成立。 给出这样的一个二叉树，你需要输出所有节点中的第二小的值。如果第二小的值不存在的话，输出 -1 。 示例 1： 输入：root = [2,2,5,null,null,5,7] 输出：5 解释：最小的值是 2 ，第二小的值是 5 。 示例 2： 输入：root = [2,2,2] 输出：-1 解释：最小的值是 2, 但是不存在第二小的值。 提示： 树中节点数目在范围 [1, 25] 内 1 <= Node.val <= 231 - 1 对于树中每个节点 root.val == min(root.left.val, root.right.val) 解法 递归的解法，go代码如下： func findSecondMinimumValue(ro....
题目描述 给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。 说明： 你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。 示例 1: 输入: root = [3,1,4,null,2], k = 1 3 / \ 1 4 \ 2 输出: 1 示例 2: 输入: root = [5,3,6,2,4,null,null,1], k = 3 5 / \ 3 6 / \ 2 4 / 1 输出: 3 解法 中序遍历 因为是二叉搜索树，树的结构是有序的。通过中序遍历可以得到一个有序数组，求第k个元素即可。 public int kthSmallest(TreeNode root, int k) { List<Integer> result = new ArrayList<>(); inOrder(root, result); return result.get(k-1); } public void inOrder(TreeNode node, List<Int....
题目描述 给定一个非空二叉树，返回其最大路径和。 本题中，路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。 示例 1： 输入：[1,2,3] 1 / \ 2 3 输出：6 示例 2： 输入：[-10,9,20,null,null,15,7] -10 / \ 9 20 / \ 15 7 输出：42 解法-递归 private int ret = Integer.MIN_VALUE; public int maxPathSum(TreeNode root) { /** 对于任意一个节点, 如果最大和路径包含该节点, 那么只可能是两种情况: 1. 其左右子树中所构成的和路径值较大的那个加上该节点的值后向父节点回溯构成最大路径 2. 左右子树都在最大路径中, 加上该节点的值构成了最终的最大路径 **/ getMax(root); return ret;....
题目描述 输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构) B是A的子结构， 即 A中有出现和B相同的结构和节点值。 例如: 给定的树 A: 3 / \ 4 5 / \ 1 2 给定的树 B： 4 / 1 返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。 示例 1： 输入：A = [1,2,3], B = [3,1] 输出：false 示例 2： 输入：A = [3,4,5,1,2], B = [4,1] 输出：true 限制： 0 <= 节点个数 <= 10000 解法 利用递归的思想解决。用A的根节点、左节点、右节点依次尝试是否等B的根节点，如果是则尝试对比下一个节点 go代码如下： func isSubStructure(A *TreeNode, B *TreeNode) bool { if A == ni....
题目 请完成一个函数，输入一个二叉树，该函数输出它的镜像。 例如输入： 4 / \ 2 7 / \ / \ 1 3 6 9 镜像输出： 4 / \ 7 2 / \ / \ 9 6 3 1 解法-递归 go代码实现如下： func mirrorTree(root *TreeNode) *TreeNode { if root == nil { return root; } var node = mirrorTree(root.Left) root.Left = mirrorTree(root.Right) root.Right = node return root } 解法-非递归（栈） 辅助栈（或队列） 利用栈（或队列）遍历树的....
题目描述 给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下： struct Node { int val; Node *left; Node *right; Node *next; } 填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。 初始状态下，所有 next 指针都被设置为 NULL。 示例： 输入：{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":null,"right":null,"val":4},"next":null,"right":{"$id":"4","left":null,"next":null,"right":null,"val":5},"val":2},"next":null,"right":{"$id":"5","left":{"$id":"6","left":null,"next":null,"right":null,"val":6},"ne....
题目 给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。 示例 : 给定二叉树 1 / \ 2 3 / \ 4 5 返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。 解法 可以将二叉树的直径转换为：二叉树的 每个节点的左右子树的高度和 的最大值。 go代码实现如下： var ans int = 0 func diameterOfBinaryTree(root *TreeNode) int { ans = 0 depth(root) return ans } func depth(node *TreeNode) int { if node == nil { return 0 } var leftDepth, rightDepth = depth(node.Left), depth(node.Right) ans = max(leftDepth + rightDepth, ans) return 1 + max(leftDepth, rightDep....
题目 给定一个二叉树，原地将它展开为一个单链表。 例如，给定二叉树 1 / \ 2 5 / \ \ 3 4 6 将其展开为： 1 \ 2 \ 3 \ 4 \ 5 \ 6 解法-递归 题目要求原地展开，故不能使用数组类变量存储全部节点值再重构树。将左右子树分别递归展开，将原左子树变为节点的右子树，再将原右子树变为当前右子树最右节点的右子树。 go代码实现 func flatten(root *TreeNode) { if root == nil { return } flat(root) } func flat(node *TreeNode) { if node == nil { return } flat(node.Left) flat(node.Right) var temp *TreeNode = node.Right node.Right, node.Left = node.Left, nil for node.Right != nil { node = node.Right } node.Right = temp } 或者简化一下代码： func flatte....
题目 将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。 本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。 示例: 给定有序数组: [-10,-3,0,5,9], 一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树： 0 / \ -3 9 / / -10 5 解法 因为左右高度不能大于1，所以可以找个中间节点，保证二叉树的平衡性。找到中间节点作为根节点，然后用递归遍历。另外需要注意的是，求中点不要用 int mid = (begin + end)/2，有溢出风险，稳妥的方法是 int mid = begin + (end-begin)/2。 go代码实现： func sortedArrayToBST(nums []int) *TreeNode { return bst(nums, 0, len(nums)-1) } func bst(nums []int, begin int, end int) *TreeNode { if begin > end { return ni....
题目描述 根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如，给出 前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树： 3 / \ 9 20 / \ 15 7 解法-递归 通过前序遍历的第一个节点可知道root节点，然后利用中序遍历，可以根据root节点把树划分为两个子树，然后递归解决 java代码实现： public TreeNode buildTree(int[] preorder, int[] inorder) { if(preorder.length==0||inorder.length==0){ return null; } TreeNode root=new TreeNode (preorder[0]); for(int i=0;i<preorder.length;i++){ if(preorder[0]==inorder[i]){ // 针对preOrder 左子树子序列（1，i+1） root.left=buildTree(Arr....
题目描述 给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。 例如： 给定二叉树 [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 返回锯齿形层次遍历如下： [ [3], [20,9], [15,7] ] 解法1-DFS 根据DFS遍历，奇数层按倒序插入。 Java代码如下： public List<List<Integer>> zigzagLevelOrder(TreeNode root) { List<List<Integer>> result = new ArrayList<>(); zLevelOrder(root, result, 0); return result; } public void zLevelOrder(TreeNode node, List<List<Integer>> result, int level) { if (node == null) { re....
题目 给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？ 示例: 输入: 3 输出: 5 解释: 给定 n = 3, 一共有 5 种不同结构的二叉搜索树: 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3 解法-动态规划 假设 n 个节点存在二叉排序树的个数是 G (n)，令 f(i) 为以 i 为根的二叉搜索树的个数，则 G(n) = f(1) + f(2) + f(3) + f(4) + ... + f(n) 当 i 为根节点时，其左子树节点个数为 i-1 个，右子树节点为 n-i，则 f(i) = G(i-1)*G(n-i)f(i)=G(i−1)∗G(n−i) 综合两个公式可以得到 卡特兰数 公式 G(n) = G(0)*G(n-1)+G(1)*G(n-2)+...+G(n-1)*G(0)G(n)=G(0)∗G(n−1)+G(1)∗G(n−2)+...+G(n−1)∗G(0) Java实现 class Solution { public int numTrees(int n) ....
题目 给定一个二叉树，判断其是否是一个有效的二叉搜索树。 假设一个二叉搜索树具有如下特征： 节点的左子树只包含小于当前节点的数。 节点的右子树只包含大于当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。 示例 1: 输入: 2 / \ 1 3 输出: true 示例 2: 输入: 5 / \ 1 4 / \ 3 6 输出: false 解释: 输入为: [5,1,4,null,null,3,6]。 根节点的值为 5 ，但是其右子节点值为 4 。 解法 比较巧妙的写法：go实现，maxInt64是因为测试用例有int64的值 package main func isValidBST(root *TreeNode) bool { return validate(root, math.MinInt64, math.MaxInt64) } func validate(node *TreeNode, min int, max int) bool { if node == nil { return true } if node....
BFS（广度优先搜索）Java public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<>(); Queue<TreeNode> queue = new ArrayDeque<>(); if (root != null) { queue.add(root); } while(!queue.isEmpty()) { int n = queue.size(); List<Integer> level = new ArrayList<>(); for(int i = 0; i<n; i++) { TreeNode node = queue.poll(); level.add(node.val); if (node.left != null) { queue.add(node.left); } if (node.right != null) { qu....