110、Balanced Binary Tree
二十六、题目
给定二叉树，确定它是否是平衡二叉树。
平衡二叉树定义为：
二叉树每个节点的两个子树的深度相差不超过1。
思路：
如果root==null，那么肯定是一个平衡二叉树。然后写一个返回二叉树高度的函数，如果根节点不为空，那么判断其左右子树的高度是否大于1，如果大于1那么肯定不是平衡二叉树，之后就是递归，判断子树的子树是否是平衡的。
Example 1:
Given the following tree
[3,9,20,null,null,15,7]
:
3
/ \
9 20
/ \
15 7
Return true.
Example 2:
Given the following tree
[1,2,2,3,3,null,null,4,4]
:
1
/ \
2 2
/ \
3 3
/ \
4 4
Return false.
package cn.hnu.leetcode.easy;
import cn.hnu.leetcode.easy.use_Class.TreeNode;
public class _110_IsBalanced {
public boolean isBalanced(TreeNode root) {
if(root == null){
return true;
}
TreeNode left = root.left;
TreeNode right = root.right;
//左右子树的深度大于1,绝对不是平衡二叉树
if(Math.abs(treeDepth(right)-treeDepth(left))>1){
return false;
}
//递归,再看根的左右子树是否满足平衡二叉树的条件,
//哪怕任何一个子树不满足平衡二叉树的条件都会返回false,所以这里是&&
return isBalanced(right)&&isBalanced(left);
}
/**
* 二叉树的高度
* @param node
* @return
*/
public static int treeDepth(TreeNode node){
if(node == null){
return 0;
}
int leftDepth = treeDepth(node.left);
int rightDepth = treeDepth(node.right);
return Math.max(leftDepth, rightDepth)+1;
}
}
111、Minimum Depth of Binary Tree
二十七、题目
给定二叉树，找到它的最小深度。
最小深度是沿从根节点到最近的叶子节点的最短路径上的节点数。
注意：叶子是没有子节点的节点
思路：
此题就是在求树的最大深度的一个特例，只是将最后的max函数改成min函数，需要考虑到的是【1,1，null】这种类型的树，它返回的最小深度是2，而不是1。
Example:
Given binary tree
[3,9,20,null,null,15,7]
,
3
/ \
9 20
/ \
15 7
return its minimum depth = 2.
package cn.hnu.leetcode.easy;
import cn.hnu.leetcode.easy.use_Class.TreeNode;
public class _111_MinDepth {
public int minDepth(TreeNode root) {
//如果根节点为空,返回0
if(root==null){
return 0;
}
//左子树的高度
int leftDepth = minDepth(root.left);
//右子树的高度
int rightDepth = minDepth(root.right);
//考虑[1,1,null]的情况
if(leftDepth==0||rightDepth==0){
return leftDepth>=rightDepth?leftDepth+1:rightDepth+1;
}
//同求树的高度一个道理,如果不加上面的判断,对于[1,1,null]的树最小高度返回的是1,而实际上是2
return Math.min(leftDepth, rightDepth)+1;
}
}
112. Path Sum
二十八、题目
给定一棵二叉树和一个值sum，确定树是否含有一条根到叶子节点路径，使得沿路径的所有值相加等于给定的那个数sum。
注意：叶子是没有子节点的节点。
思路：
详见代码，依旧递归。
Example:
Given the below binary tree and
sum = 22
,
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
return true, as there exist a root-to-leaf path
5->4->11->2
which sum is 22.
package cn.hnu.leetcode.easy;
import cn.hnu.leetcode.easy.use_Class.TreeNode;
public class _112_HasPathSum {
private boolean stop = false;
public boolean hasPathSum(TreeNode root, int sum) {
//设置一个函数,只为了该表stop的值
hasLine(root,0,sum);
return stop;
}
/**
* 判断直到叶子节点,是否找到了这样的一条路径,使路径上的所有节点的值相加==num
* @param node
* @param cur
* @param sum
*/
private void hasLine(TreeNode node, int cur, int sum) {
//只要stop!=true并且节点不为空,就一直递归下去
if(!stop&&node!=null){
//到达叶子节点,判断路径上的节点的值相加是否==num,如果等于，就结束了
if(node.left==null&&node.right==null&&node.val+cur==sum){
stop = true;
}
//如果左子树不为空,递归;传入的变量,变成该节点的左孩子,并将该节点的值加上cur递归回去
if(node.left!=null){
hasLine(node.left, cur+node.val, sum);
}
//如果右子树不为空,递归;同上
if(node.right!=null){
hasLine(node.right, cur+node.val, sum);
}
}
}
}
118、Pascal's Triangle
二十九、题目
给定非负整数numRows，生成一个杨辉三角，显示每一行的数字
思路：
杨辉三角的问题，把整个杨辉三角想成一个管子，管子里再放入一节一节管子，用链表的思想做，详情键代码。
Example:
Input: 5
Output:
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]
package cn.hnu.leetcode.easy;
import java.util.LinkedList;
import java.util.List;
public class _118_Generate {
public List<List<Integer>> generate(int numRows) {
//创建一个链表存储最终的结果
LinkedList<List<Integer>> resList = new LinkedList<List<Integer>>();
//如果输入的行数小于等于0,直接返回未初始化的resList
if(numRows<=0){
return resList;
}
//设置链表中的链表,表示前一个链表
LinkedList<Integer> preList = new LinkedList<Integer>();
//第一个链表,元素就只有一个1
preList.add(1);
//将这个第一个链表放入结果集链表
resList.add(preList);
//如果输入的行数是1,那么进不了for循环,返回的就是一个包含1的链表放在最终的结果链表中
//行数大于等于2的时候进入循环
for(int i = 1;i<numRows;i++){
//设置一个当前链表,用于存储当前的结果集
LinkedList<Integer> curList = new LinkedList<Integer>();
//首先在当前链表的首端添加1
curList.add(1);
//上一个链表的大小
int size = preList.size();
//如果上一个链表的大小只是1,进不了循环,那么这个循环过后,直接在当前链表的末尾再添加1
//如果当前链表的大小大于1,即从第三行开始才进入这个循环
for(int j = 1;j<size;j++){
curList.add(preList.get(j-1)+preList.get(j));
}
//在当前链表的最后再添加1
curList.add(1);
//当前链表被设定为上一个链表
preList=curList;
//将当前链表放入结果链表中
resList.add(curList);
}
//返回结果链表
return resList;
}
}
119、Pascal's Triangle II
三十、题目
给定非负整数k，其中k≤33，返回杨辉三角形的第k个行的所有元素
请注意，行索引从0开始。
思路：
同上，就是多了一步取出哪一行的操作。
Example:
Input: 3
Output: [1,3,3,1]
方法一：
package cn.hnu.leetcode.easy;
import java.util.LinkedList;
import java.util.List;
public class _119_GetRow {
public List<Integer> getRow(int rowIndex) {
//创建一个resList存储结果链表,它用于存储杨辉三角的每一行,而每一行又是一个链表
LinkedList<List<Integer>> resList = new LinkedList<>();
//创建一个前置链表,标识resList中前一行数字
LinkedList<Integer> preList = new LinkedList<Integer>();
//如果rowIndex是负数,直接返回resList的首元素,它并没有初始化，所有只会返回空
if(rowIndex<0){
return resList.get(0);
}
//否则就在preList中添加元素1
preList.add(1);
//再将preList放在resList中
resList.add(preList);
//只有当RowIndex>=1时,才能进入循环
for(int i = 0;i<rowIndex;i++){
//设置一个curList,标识杨辉三角当前的一行元素
LinkedList<Integer> curList = new LinkedList<Integer>();
//首先在这个当前一行添加元素1
curList.add(1);
//如果是第三行,也就是rowIndex>=3时,才能进入以下循环
for(int j = 1;j<preList.size();j++){
curList.add(preList.get(j-1)+preList.get(j));
}
//无论与否,都在每一行的末尾添加元素1
curList.add(1);
//然后将当前的一行,也放进resList中
resList.add(curList);
//并将当前这一行设置成上一行,继续进行外层for循环,计算下一行
preList = curList;
}
//最后就是要哪一行返回哪一行
return resList.get(rowIndex);
}
}
方法二：
package cn.hnu.leetcode.easy;
import java.util.LinkedList;
import java.util.List;
public class _119_GetRow {
public List<Integer> getRow(int rowIndex) {
//创建一个list只用于存储每一行
LinkedList<Integer> list = new LinkedList<Integer>();
//因为rowIndex是非负的,所以不用考虑负数的情况
//第0行就是第一行
//首先添加一个1
list.add(1);
//如果rowIndex==0,直接返回即可
if(rowIndex==0){
return list;
}
//否则继续添加1
list.add(1);
//如果是第二行也是直接返回
if(rowIndex==1){
return list;
}
//第三行开始进入for循环
for(int i = 2;i<=rowIndex;i++){
//先在链表尾部添加元素1
list.add(1);
//每次都在链表的第二个位置开始设置元素 ,值就是相当于其"肩上"两个元素和的形式
/**
过程：
1
1 1
1 1 1 --> 1 2 1
1 2 1 1 --> 1 3 3 1
1 3 3 1 1 --> 1 4 6 4 1
*/
for(int j = i-1;j>0;j--){
list.set(j, list.get(j-1)+list.get(j));
}
}
return list;
}
}