读一读
给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
例如：
给定二叉树 [3,9,20,null,null,15,7],
3 / \ 9 20 / \ 15 7
返回其自底向上的层次遍历为：
[ [15,7], [9,20], [3] ]
/**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public IList<IList<int>> LevelOrderBottom(TreeNode root) {
IList<IList<int>> res = new List<IList<int>>();
Queue<TreeNode> q = new Queue<TreeNode>();
q.Enqueue(root);
while(q.Count > 0)
{
IList<int> data = new List<int>();
int count = q.Count;//临时保存某层的数量
//一下子将这层遍历完，然后队列里的就全是下一层的了
for(int i = 0;i<count;i++)
{
TreeNode node = q.Dequeue();
if(node == null) continue;
data.Add(node.val);
q.Enqueue(node.left);//随便加进去啦
q.Enqueue(node.right);
}
if(data.Count > 0)
res.Insert(0,data);
}
return res;
}
}
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
1 / \ 2 2 / \ / \ 3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1 / \ 2 2 \ \ 3 3
迭代的方式
/**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int x) { val = x; }
* }
*/
public bool IsSymmetric(TreeNode root) {
if(root == null) return true;
//两条队列
Queue<TreeNode> left = new Queue<TreeNode>();
Queue<TreeNode> right = new Queue<TreeNode>();
left.Enqueue(root.left);
right.Enqueue(root.right);
while(left.Count > 0 && left.Count == right.Count)
{
//保证左边的结点，对上的是右边的结点
TreeNode l = left.Dequeue();
TreeNode r = right.Dequeue();
if(l == null && r == null) continue;
if(l == null || r == null) return false;
if(l.val == r.val)
{
left.Enqueue(l.left);//左边的先左后右
left.Enqueue(l.right);
right.Enqueue(r.right);//右边的先右后左
right.Enqueue(r.left);
}
else
{
return false;
}
}
return left.Count == right.Count;
}递归的方式：
public class Solution {
public bool IsSymmetric(TreeNode root) {
return IsSymmetric(root,root);
}
public bool IsSymmetric(TreeNode one,TreeNode two)
{
//前两个判断可以保证one和two都不为null
if(one == null && two == null) return true;
if(one == null || two == null) return false;
return (one.val == two.val) && IsSymmetric(one.left,two.right) && IsSymmetric(one.right,two.left);
}
}
给定两个二进制字符串，返回他们的和（用二进制表示）。
输入为非空字符串且只包含数字 1 和 0。
示例 1:
输入: a = "11", b = "1"输出: "100"
示例 2:
输入: a = "1010", b = "1011"输出: "10101"
public string AddBinary(string a, string b) {
StringBuilder res = new StringBuilder();
int aLen = a.Length;
int bLen = b.Length;
int up = 0;
int index = 0;
int temp = 0;
while(index < aLen || index < bLen)
{
temp = 0;
if(index < aLen)
{
temp += a[aLen - index - 1] - '0';//转化为数字0和1
}
if(index < bLen)
{
temp += b[bLen - index - 1] - '0';//转换为数字0和1
}
temp += up;//加上进位值
up = temp / 2;//是否进位
temp = temp % 2;//当前位置的值
res.Insert(0,(char)(temp + '0'));
index++;//向前推进
}
if(up > 0)
{
res.Insert(0,'1');//最后处理没处理到的进位
}
return res.ToString();
}
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,1]输出: 1
示例 2:
输入: [4,1,2,1,2]输出: 4
public int SingleNumber(int[] nums) {
int xor = 0;
for(int i = 0;i<nums.Length;i++)
{
//对同一个元素的两次异或操作等同于+1又-1那样
xor ^= nums[i];
}
return xor;
}因为是由0开始，任何数与0的异或都是等于它本身，而任何数与自己异或都是等于0的，所以数据中所有两个相同的数之间的异或都变成0了，最后那个唯一的元素和0异或操作，还是等于它本身就是结果了。
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树 [3,9,20,null,null,15,7],
3 / \ 9 20 / \ 15 7
返回它的最小深度 2.
public int MinDepth(TreeNode root) {
if(root == null)
{
return 0;
}
//根节点不能算是叶节点的情况
if(root.left == null)
{
return MinDepth(root.right) + 1;
}
if(root.right == null)
{
return MinDepth(root.left) + 1;
}
return Math.Min(MinDepth(root.left),MinDepth(root.right)) + 1;
}
给定一个正整数，返回它在 Excel 表中相对应的列名称。
例如，
1 -> A 2 -> B 3 -> C ... 26 -> Z 27 -> AA 28 -> AB ...
示例 1:
输入: 1输出: "A"
示例 2:
输入: 28输出: "AB"
示例 3:
输入: 701输出: "ZY"
public string ConvertToTitle(int n) {
StringBuilder res = new StringBuilder();
int temp = 0;
while(n > 0)
{
temp = n % 26;
n = n / 26;
if(temp == 0)
{
//特殊的26的倍数处理
temp = 26;
n = n - 1;
}
res.Insert(0,((char)(temp+64)));
}
return res.ToString();
}
给定一个Excel表格中的列名称，返回其相应的列序号。
例如，
A -> 1 B -> 2 C -> 3 ... Z -> 26 AA -> 27 AB -> 28 ...
示例 1:
输入: "A"输出: 1
示例 2:
输入: "AB"输出: 28
示例 3:
输入: "ZY"输出: 701
public int TitleToNumber(string s) {
int res = 0;
for(int i = 0;i<s.Length;i++)
{
res = res * 26 + s[i] - 'A' + 1;
}
return res;
}可以把它想象成是一个26进1的数字，但是又有点不同。
给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在众数。
示例 1:
输入: [3,2,3] 输出: 3
示例 2:
输入: [2,2,1,1,1,2,2] 输出: 2
public int MajorityElement(int[] nums) {
int i = 0;//假设的众数指标
int j = 1;//进度指标
int count = 0;//计数
//计数超过一半前
while(count < (nums.Length - i)/2 && j < nums.Length)
{
if(nums[j] == nums[i])
{
count++;
}
else
{
count--;
}
if(count == -1)
{
//前面为成对不相等的值，抛弃掉，重新计数
i = j + 1;
j = i + 1;
count = 0;
}
else
{
j++;//进度向前
}
}
return nums[i];
}解析请查看主元素问题
给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。
在杨辉三角中，每个数是它左上方和右上方的数的和。
示例:
输入: 5输出:[ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ]
public IList<IList<int>> Generate(int numRows) {
IList<IList<int>> datas = new List<IList<int>>();
if(numRows == 0) return datas;
IList<int> data = new List<int>();
data.Add(1);//第0行特殊化处理
datas.Add(data);
for(int i = 1;i < numRows;i++)
{
data = new List<int>();
data.Add(1);
for(int j = 1;j < i;j++)
{
data.Add(datas[i-1][j] + datas[i-1][j-1]);
}
data.Add(1);
datas.Add(data);
}
return datas;
}
给定两个二叉树，编写一个函数来检验它们是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例 1:
输入: 1 1 / \ / \ 2 3 2 3 [1,2,3], [1,2,3] 输出: true
示例 2:
输入: 1 1 / \ 2 2 [1,2], [1,null,2] 输出: false
示例 3:
输入: 1 1 / \ / \ 2 1 1 2 [1,2,1], [1,1,2] 输出: false
public bool IsSameTree(TreeNode p, TreeNode q) {
//边界，递归到叶节点的子节点
if(p == null && q == null) return true;
//安全判断的同时也可以判断是否相同，保证p和q都不为空
if(p == null || q == null) return false;
bool left = IsSameTree(p.left,q.left);//递归对比每一个左子树
bool right = IsSameTree(p.right,q.right);//递归对比每一个右子树
//结合每一个左子树和右子树的对比结果，还有根节点的对比
return left && right && (p.val == q.val);
}
//一次过，这是我没想到的，哈哈哈。