题目简介:给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。
说明:解集不能包含重复的子集。
示例:
123456789101112输入: nums = [1,2,3]输出:[ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], []]
思路:回溯,每次从上个元素的下一个位置开始搜索即可。
代码如下:12345678910111213141516171819202122232425262728class Solution {public: vector<vector<int>...
题目简介:计算给定二叉树的所有左叶子之和。
示例:
1234567 3 / \ 9 20 / \ 15 7在这个二叉树中,有两个左叶子,分别是 9 和 15,所以返回 24
思路:在递归的时候设置一个flag,只有当前结点为叶子结点且是上层结点的左孩子时才将结点值加入sum中。
tip:
只有一个结点时,该结点不算左孩子。
代码如下:123456789101112131415161718192021222324252627282930313233/** * Definition for a binary tree node. * struct TreeN...
题目简介:给定一个可包含重复数字的序列,返回所有不重复的全排列。
示例:
1234567输入: [1,1,2]输出:[ [1,1,2], [1,2,1], [2,1,1]]
思路:回溯+深搜,为了方便操作,先将数组排序。
为了去除重复,当nums[i] == nums[i - 1] && !visit[i - 1]时,说明目前的元素nums[i]所要经历的遍历,之前的元素nums[i - 1]已经经历过一遍了,所以直接continue即可。
代码如下:1234567891011121314151617181920212223242526272829303132333...
题目简介:在本问题中,有根树指满足以下条件的有向图。该树只有一个根节点,所有其他节点都是该根节点的后继。每一个节点只有一个父节点,除了根节点没有父节点。
输入一个有向图,该图由一个有着N个节点 (节点值不重复1, 2, …, N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间,这条附加的边不属于树中已存在的边。
结果图是一个以边组成的二维数组。 每一个边 的元素是一对 [u, v],用以表示有向图中连接顶点 u 和顶点 v 的边,其中 u 是 v 的一个父节点。
返回一条能删除的边,使得剩下的图是有N个节点的有根树。若有多个答案,返回最后出现在给定二维数组的答案。
示例 1...
题目简介:翻转一棵二叉树。
示例:
输入:
12345 4 / \ 2 7 / \ / \1 3 6 9
输出:
12345 4 / \ 7 2 / \ / \9 6 3 1
思路:相当于中序遍历,从根节点出发,将左右子树互换即可。
代码如下:1234567891011121314151617181920212223242526272829303132/** * Definition for a binary tree node. * struct TreeNode { * int val; *...
题目简介:编写一个程序,通过已填充的空格来解决数独问题。
一个数独的解法需遵循如下规则:
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用 '.' 表示。
一个数独。
...
题目简介:给定一个二叉树,返回它的中序 遍历。
示例:
12345678输入: [1,null,2,3] 1 \ 2 / 3输出: [1,3,2]
进阶: 递归算法很简单,你可以通过迭代算法完成吗?
思路:先用递归做着,以后补迭代做法(将栈显示的表达出来)。
代码如下:12345678910111213141516171819202122232425262728293031323334/** * Definition for a binary tree node. * struct TreeNode { * int val; * Tr...
题目简介:给定一个二维网格和一个单词,找出该单词是否存在于网格中。
单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例:
12345678910board =[ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E',&ap...
题目简介:给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。
示例 1:
123456789输入: 3 / \ 9 20 / \ 15 7 输出:[3, 14.5, 11]解释:第 0 层的平均值是 3 , 第1层是 14.5 , 第2层是 11 。因此返回 [3, 14.5, 11] 。
提示:
节点值的范围在32位有符号整数范围内。
思路:广搜,每次出队前先记录当前队列的大小,即该层的结点数量。
tip:
需要使用long来存储sum,否则会溢出。
代码如下:123456789101112131415161718192021222...
题目简介:找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数,并且每种组合中不存在重复的数字。
说明:
所有数字都是正整数。
解集不能包含重复的组合。
示例 1:
12输入: k = 3, n = 7输出: [[1,2,4]]
示例 2:
12输入: k = 3, n = 9输出: [[1,2,6], [1,3,5], [2,3,4]]
思路:依然是回溯的做法,当元素数量 > k 或 和大于 n 时,直接return即可。
需要注意的是要从上个元素的下一个位置开始遍历(不能取重复的数字)。
代码如下:1234567891011121314151...