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;
}
}