Leetcode 96：不同的二叉搜索树 题目描述 给定一个整数n，求以1...n为节点的二叉搜索树有多少种？ 示例 解题思路 可以使用动态规划解，但是这个题同样也是一个卡塔兰数问题。卡塔兰数的应用主要有：找零钱问题、三角网格问题、括号排列问题、球盒问题等。卡塔兰数的数学表达式为 所以代码只需要实现这个式子即可，时间复杂度为O(n)，空间复杂度为O(1)。 代码实现 int numTrees(int n) {     long long C = 1;     for (int i = 0; i < n; ++…

Leetcode 101：对称二叉树 题目描述 给定一个二叉树，检查它是否是镜像对称的。 解题思路 既然它是镜像的话，那么就是左右对称，这个我们可以使用一个递归来解决。我们令A等于这个树，B也等于这个树，假设A树和B树都只有一个结点（空结点也看做是一个结点）其实也就是两个树中至少一个树为NULL的时候，结果只会存在三种情况： 1.A的该结点为NULL，B的该结点也为NULL，即都是空结点，那么这两个树相等，自然是镜像，返回true； 2.A的该结点为NULL，B的该结点不为NULL（或者A的该结点不是NULL，B的…

Leetcode 105：重建二叉树 题目描述 根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 示例 给出 前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树： 3 / \ 9 20 / \ 15 7 题目解析 我们根据前序遍历的特点可以发现，前序遍历的第一个数字一定是这个二叉树的根节点；然后根据中序遍历的特点可发现，根节点左侧的数字一定是左子树，右侧一定是右子树。然后将中序遍历以根节点为中心划分…

Leetcode 124：二叉树中的最大路径和 题目描述 给定一个非空二叉树，返回其最大路径和。本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。 解题思路 参见： https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/solution/er-cha-shu-zhong-de-zui-da-lu-jing-he-by-ikaruga/ 代码实现 int maxSum(TreeNode* r…

Leetcode 136：只出现一次的数字 题目描述 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。 说明： 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？ 示例 输入: [2,2,1] 输出: 1 解题思路 这里我们可以利用异或的原理，我们发现在异或中： a⊕0=a；a⊕a=0。a⊕b⊕a=(a⊕a)⊕b=0⊕b=b 所以我们只需要将所有的数进行 XOR 操作，得到那个唯一的数字。 代码实现 int singleNumber(vector&…

Leetcode 142：环形链表2 题目描述 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。 说明：不允许修改给定的链表。 题目解析 《剑指offer》中也有此题，所以直接复制过来予以说明。 其实我的思路是把每个访问过的结点做标记，然后不断往下走后，遇到的第一个标记过的点，就是还的入口结点，如果没有遇到，则就不存在环，返回null。但是这…

Leetcode 148：排序链表 题目描述 在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。 示例 示例 1: 输入: 4->2->1->3 输出: 1->2->3->4 示例 2: 输入: -1->5->3->4->0 输出: -1->0->3->4->5 解题思路 由于题目要求复杂度为O(nlogn)且空间复杂度为常数级，我们可以想到的是堆排序，但是实际上，由于是链表，其不需要借助额外的数组来存储内容，只需要通过链表直接的链接调整即可，所以对于链表来说，归并排序的空间复杂度也是O(1…