LeetCode 第 104 題：二叉樹的最大深度
提示：思路1：后序遍歷：看完左右子樹合溺，才能計(jì)算自己毁欣；
思路2：使用 BFS庇谆。
LeetCode 第 111題：二叉樹的最小深度
提示：思路1：BFS 就可以做，并且我覺得思路更直接一些凭疮。并且求二叉樹的最小深度也是這個(gè)套路饭耳。
思路2：使用遞歸的話，注意只有左子樹或者只有右子樹的情況
Python 代碼：
class Solution(object):
def minDepth(self, root):
if root is None:
return 0
depth = 0
queue = [root]
while queue:
depth += 1
size = len(queue)
for _ in range(size):
first = queue.pop(0)
if first.left is None and first.right is None:
return depth
if first.left:
queue.append(first.left)
if first.right:
queue.append(first.right)
LeetCode 第 226 題：反轉(zhuǎn)一棵二叉樹
image-20181214103339221
LeetCode 第 100 題：判斷兩個(gè)二叉樹是否一樣
image-20181214103315065
LeetCode 第 101 題：檢查一棵樹是否是鏡像對稱的
提示：首先理解什么是鏡面對稱执解。兩個(gè)結(jié)點(diǎn)的根結(jié)點(diǎn)的值必須相等寞肖，并且1、左邊的左結(jié)點(diǎn)=右邊的右結(jié)點(diǎn)衰腌；2新蟆、左邊的右結(jié)點(diǎn)=右邊的左結(jié)點(diǎn)。我覺得沒有什么技巧右蕊，記住就可以了琼稻。使用下面這張圖思考這個(gè)問題。
思路1：遞歸饶囚。
image-20181214103655847
思路2：雙端隊(duì)列帕翻。
image-20181214104909130
Python 代碼：
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution(object):
def isSymmetric(self, root):
# 先寫遞歸終止條件
if root is None:
return True
# 其實(shí)應(yīng)該用 from collections import deque
deque = []
deque.insert(0, root.left)
deque.append(root.right)
while deque:
l_node = deque.pop(0)
r_node = deque.pop()
if l_node is None and r_node is None:
continue
if l_node is None or r_node is None:
return False
if l_node.val != r_node.val:
return False
deque.insert(0, l_node.right)
deque.insert(0, l_node.left)
deque.append(r_node.left)
deque.append(r_node.right)
return True
LeetCode 第 222 題：給出一個(gè)完全二叉樹，求出該樹的節(jié)點(diǎn)個(gè)數(shù)（典型遞歸問題）
提示：如果是滿二叉樹坯约，結(jié)點(diǎn)的個(gè)數(shù)是有規(guī)律可循的熊咽。那么是不是滿二叉樹，可以通過子樹的深度來判斷闹丐。
Python 代碼：
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def countNodes(self, root):
"""
:type root: TreeNode
:rtype: int
"""
left_depth = self.__depth(root, True)
right_depth = self.__depth(root, False)
if left_depth == right_depth:
# return 2 ** left_depth - 1
return (1 << left_depth) - 1
if left_depth > right_depth:
return 1 + self.countNodes(root.left) + self.countNodes(root.right)
def __depth(self, node, is_left):
depth = 0
while node:
depth += 1
node = node.left if is_left else node.right
return depth
LeetCode 第 110 題：是否是平衡二叉樹
一棵高度平衡二叉樹定義為：一個(gè)二叉樹每個(gè)節(jié)點(diǎn) 的左右兩個(gè)子樹的高度差的絕對值不超過 1 横殴。
Python 代碼：使用后序遍歷
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
# 給定一個(gè)二叉樹，判斷它是否是高度平衡的二叉樹。
# 本題中衫仑，
class Solution:
def isBalanced(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
# 先寫特殊情況梨与，空樹是平衡二叉樹
if root is None:
return True
return self.__helper(root) != -1
def __helper(self, node):
# 因?yàn)楸仨殢牡紫碌缴厦嬉来闻袛啵允褂煤笮虮闅v
if node is None:
return 0
left = self.__helper(node.left)
right = self.__helper(node.right)
if left == -1 or right == -1 or abs(left - right) > 1:
return -1
# 重點(diǎn)文狱，輔助函數(shù)的定義是粥鞋，左右子樹的高度中最大的那個(gè)
return max(left, right) + 1
LeetCode 第 112 題：Path Sum
Python 代碼：
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def hasPathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: bool
"""
if root is None:
return False
# 此時(shí) root 不為空
# 左邊看一看，右邊看一看
# 【重點(diǎn)】一定要記得判斷瞄崇，左邊子樹和右邊子樹同時(shí)為空呻粹，說明走到底了
if root.left is None and root.right is None and root.val == sum:
return True
left_has = self.hasPathSum(root.left, sum - root.val)
right_has = self.hasPathSum(root.right, sum - root.val)
return left_has or right_has
LeetCode 第 404 題：計(jì)算左邊葉子結(jié)點(diǎn)數(shù)值之和
Python 代碼：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# 關(guān)鍵在于判斷是否是左邊葉子結(jié)點(diǎn)
def sumOfLeftLeaves(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if root is None:
return 0
# 判斷左邊葉子結(jié)點(diǎn)是關(guān)鍵
if root.left is not None and root.left.left is None and root.left.right is None:
return root.left.val + self.sumOfLeftLeaves(root.right)
return self.sumOfLeftLeaves(root.left) + self.sumOfLeftLeaves(root.right)
LeetCode 第 257 題：得到二叉樹的所有路徑。
給定一個(gè)二叉樹苏研，返回所有從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑批幌。
傳送門：https://leetcode.com/problems/binary-tree-paths/description/
分析：典型的回溯犁罩。下面的這個(gè)寫法比較奇怪。
Java 代碼：
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> res = new ArrayList<>();
if (root == null) {
return res;
}
// 這個(gè)節(jié)點(diǎn)是個(gè)根節(jié)點(diǎn)，想一想只有一個(gè)元素的情況
if (root.left == null && root.right == null) {
res.add(String.valueOf(root.val));
}
List<String> leftS = binaryTreePaths(root.left);
for (int i = 0; i < leftS.size(); i++) {
res.add(String.valueOf(root.val) + "->" + leftS.get(i));
}
List<String> rightS = binaryTreePaths(root.right);
for (int i = 0; i < rightS.size(); i++) {
res.add(String.valueOf(root.val) + "->" + rightS.get(i));
}
return res;
}
}
心得：分析遞歸關(guān)系是這道題的難點(diǎn)意推。
LeetCode 第 113 題：給定一棵二叉樹司训，返回所有從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑颜启，并且要等于指定的和
Python 代碼：
class Solution(object):
def pathSum(self, root, sum):
results = []
self.__dfs([], root, sum, results)
return results
def __dfs(self, path, root, sum, results):
if root is None:
return
if root.left is None and root.right is None and root.val == sum:
result = []
result.extend(path)
result.append(root.val)
results.append(result)
return
path.append(root.val)
if root.left:
self.__dfs(path, root.left, sum - root.val, results)
if root.right:
self.__dfs(path, root.right, sum - root.val, results)
# 這一步很關(guān)鍵
path.pop()
LeetCode 第 113 題：路徑總和 II
要求：給定一個(gè)二叉樹和一個(gè)目標(biāo)和塞颁，找到所有從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)路徑總和等于給定目標(biāo)和的路徑。
說明: 葉子節(jié)點(diǎn)是指沒有子節(jié)點(diǎn)的節(jié)點(diǎn)大渤。
要特別注意彈出制妄，即回溯的過程。
Java 代碼：
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public class Solution {
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) {
return result;
}
// 根節(jié)點(diǎn)
if (root.left == null && root.right == null) {
if (root.val == sum) {
List<Integer> temp1 = new ArrayList<>();
temp1.add(root.val);
result.add(temp1);
return result;
}
}
List<List<Integer>> leftLists = pathSum(root.left, sum - root.val);
mergeOneAndList(root, leftLists, result);
List<List<Integer>> rightLists = pathSum(root.right, sum - root.val);
mergeOneAndList(root, rightLists, result);
return result;
}
private void mergeOneAndList(TreeNode node, List<List<Integer>> listList, List<List<Integer>> result) {
for (int i = 0; i < listList.size(); i++) {
List<Integer> temp1 = new ArrayList<>();
temp1.add(node.val);
temp1.addAll(listList.get(i));
result.add(temp1);
}
}
}
題后總結(jié)：使用遞歸的方法解決問題泵三，很多時(shí)候忍捡，并不是讓我們真正地去做這個(gè)問題，而是須要我們發(fā)現(xiàn)遞歸關(guān)系切黔，尋找遞歸終止條件。歷史上類似的經(jīng)典問題有漢諾塔問題和八皇后問題具篇。
但是纬霞，我自己覺得，我的解法驱显，尤其是在 mergeOneAndList() 函數(shù)的部分稍顯復(fù)雜诗芜。
下面給出一種簡介的解法：這種解法顯得更自然一些，遍歷了從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的每一個(gè)節(jié)點(diǎn)埃疫，然后累加計(jì)算加到了多少伏恐，這是與老師的思路不同的一種思路。
public class Solution2 {
private List<List<Integer>> result = new ArrayList<>();
public List<List<Integer>> pathSum(TreeNode root, int sum) {
getSum(root, new ArrayList<Integer>(), 0, sum);
return result;
}
private void getSum(TreeNode node, ArrayList<Integer> list, int current, int sum) {
if (node == null) {
return;
}
current += node.val;
list.add(node.val);
if (node.left == null && node.right == null) {
if (current == sum) {
result.add(list);
} else {
// 什么都不做
// 在這里可以把不滿足的節(jié)點(diǎn)都遍歷出來
return;
}
}
if (node.left != null) {
getSum(node.left, new ArrayList<Integer>(), current, sum);
}
if (node.right != null) {
getSum(node.right, new ArrayList<Integer>(), current, sum);
}
}
}
LeetCode 第 129 題：給定一棵二叉樹栓霜，每個(gè)節(jié)點(diǎn)只包含數(shù)字 0-9翠桦，從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的每條路徑可以表示成一個(gè)數(shù)，求這些數(shù)的和
Python 代碼：
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def sumNumbers(self, root):
res = []
self.__dfs(root, 0, res)
return sum(res)
# Python 中對于基礎(chǔ)的數(shù)據(jù)類型是值傳遞，即復(fù)制
def __dfs(self, root, cum_sum, res):
if root is None:
return None
if root.left is None and root.right is None:
# 結(jié)算
res.append(cum_sum * 10 + root.val)
return
self.__dfs(root.left, cum_sum * 10 + root.val, res)
self.__dfs(root.right, cum_sum * 10 + root.val, res)
LeetCode 第 437 題：路徑總和 III（重點(diǎn)销凑，遞歸丛晌，二叉樹典型處理思路）
提示：使用雙重遞歸。
傳送門：437. 路徑總和 III斗幼。
給定一個(gè)二叉樹澎蛛，它的每個(gè)結(jié)點(diǎn)都存放著一個(gè)整數(shù)值。
找出路徑和等于給定數(shù)值的路徑總數(shù)蜕窿。
路徑不需要從根節(jié)點(diǎn)開始谋逻，也不需要在葉子節(jié)點(diǎn)結(jié)束，但是路徑方向必須是向下的（只能從父節(jié)點(diǎn)到子節(jié)點(diǎn)）桐经。
二叉樹不超過1000個(gè)節(jié)點(diǎn)毁兆，且節(jié)點(diǎn)數(shù)值范圍是 [-1000000,1000000] 的整數(shù)。
示例：
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8 10 / \ 5 -3 / \ \ 3 2 11 / \ \ 3 -2 1 返回 3次询。和等于 8 的路徑有: 1. 5 -> 3 2. 5 -> 2 -> 1 3. -3 -> 11
Python 代碼：參考資料：花花醬：https://zxi.mytechroad.com/blog/tree/leetcode-437-path-sum-iii/
image-20190213071747921
Python 代碼：
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def pathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: int
"""
from collections import defaultdict
memo = defaultdict(int)
# 記憶化遞歸荧恍，memo 表示緩存
memo[0] = 1 # 表示 cur - sum = 0, return 1
self.res = 0
def helper(root, curSum):
if root is None:
return
curSum += root.val
self.res += memo[curSum - sum]
memo[curSum] += 1
helper(root.left, curSum)
helper(root.right, curSum)
memo[curSum] -= 1
helper(root, 0)
return self.res
Java 代碼：
public class Solution {
public int pathSum(TreeNode root, int sum) {
if(root == null)
return 0;
return dfs(root, sum)+pathSum(root.left, sum)+pathSum(root.right, sum);
}
private int dfs(TreeNode root, int sum){
int res = 0;
if(root == null)
return res;
if(sum == root.val)
res++;
res+=dfs(root.left,sum - root.val);
res+=dfs(root.right,sum - root.val);
return res;
}
}
LeetCode 第 235 題：二叉搜索樹的最近公共祖先
LeetCode 第 98 題：是否是二分搜索樹
提示：思路1：中序遍歷一遍就可以了；思路2：模擬系統(tǒng)棧屯吊。
Java 代碼：
class Solution {
double last = -Double.MAX_VALUE;
public boolean isValidBST(TreeNode root) {
if (root == null) {
return true;
}
if (isValidBST(root.left)) {
if (last < root.val) {
last = root.val;
return isValidBST(root.right);
}
}
return false;
}
}
LeetCode 第 450 題 ：刪除二叉搜索樹中的節(jié)點(diǎn)（一定要會Ｋ脱病）
LeetCode 第 108 題：將有序數(shù)組轉(zhuǎn)換為二叉搜索樹
LeetCode 第 230 題：二叉搜索樹中第 K 小的元素
思路1：遞歸。
思路2：用模擬系統(tǒng)棧盒卸。
LeetCode 第 236 題：二叉樹的最近公共祖先
LeetCode 第 297 題：二叉樹的序列化與反序列化
傳送門：二叉樹的序列化與反序列化骗爆。同《劍指 Offer 》第 37 題。
使用前序遍歷和中序遍歷的結(jié)果還原一棵二叉樹蔽介。
LeetCode 第 703 題：數(shù)據(jù)流中的第 k 大元素
下面的問題都來自 BST（二分搜索樹）摘投。
LeetCode 第 235 題：二分搜索樹的最近公共祖先
LeetCode 第 450 題：刪除一個(gè)二分搜索樹的結(jié)點(diǎn)（必會，不難虹蓄，多寫幾遍）
LeetCode 第 108 題：將有序數(shù)組轉(zhuǎn)換為二叉搜索樹
LeetCode 第 203 題：二叉搜索樹中第 K 小的元素
LeetCode 第 236 題：二叉樹的最近公共祖先
LeetCode 第 96 題：
要求：給定一個(gè)整數(shù) n犀呼，求以 1 ... n 為節(jié)點(diǎn)組成的二叉搜索樹有多少種？
示例:
輸入: 3
輸出: 5
解釋:
給定 n = 3, 一共有 5 種不同結(jié)構(gòu)的二叉搜索樹:
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
分析：使用動態(tài)規(guī)劃薇组。
image-20190114163626332
Python 代碼：
class Solution:
def numTrees(self, n):
"""
:type n: int
:rtype: int
"""
if n == 0 or n == 1:
return 1
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1
for i in range(2, n + 1):
for j in range(i):
dp[i] += dp[j] * dp[i - j - 1]
return dp[n]
Java 代碼：
public class Solution {
public int numTrees(int n) {
int[] dp = new int[n + 1];
// 想清楚這個(gè)值很關(guān)鍵
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
// 這里 j 表示左子樹的元素個(gè)數(shù)外臂，最小是 0 ，最大是 i-1
// 左邊子樹 + 右邊子樹 = i - 1
// i - j - 1 表示的是右邊子樹元素個(gè)數(shù)
for (int j = 0; j < i; j++) {
// 使用 * 是因?yàn)槌朔ㄓ?jì)數(shù)原理
dp[i] += dp[j] * dp[i - j - 1];
}
}
return dp[n];
}
public static void main(String[] args) {
Solution solution = new Solution();
int n = 3;
int numTrees = solution.numTrees(n);
System.out.println(numTrees);
}
}
LeetCode 第 95 題：不同的二叉搜索樹 II
要求：給定一個(gè)整數(shù) n律胀，生成所有由 1 ... n 為節(jié)點(diǎn)所組成的二叉搜索樹宋光。
示例:
輸入: 3
輸出:
[
[1,null,3,2],
[3,2,null,1],
[3,1,null,null,2],
[2,1,3],
[1,null,2,null,3]
]
解釋:
以上的輸出對應(yīng)以下 5 種不同結(jié)構(gòu)的二叉搜索樹：
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
分治算法：
# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def generateTrees(self, n):
"""
:type n: int
:rtype: List[TreeNode]
"""
res = []
if n <= 0:
return res
return self.helper(1, n)
def helper(self, left, right):
res = []
if left > right:
# 說明不構(gòu)成區(qū)間，應(yīng)該返回空結(jié)點(diǎn)
res.append(None)
return res
elif left == right:
res.append(TreeNode(left))
return res
else:
for i in range(left, right + 1):
left_sub_tree = self.helper(left, i - 1)
right_sub_tree = self.helper(i + 1, right)
for l in left_sub_tree:
for r in right_sub_tree:
root = TreeNode(i)
root.left = l
root.right = r
res.append(root)
return res
動態(tài)規(guī)劃：這個(gè)解法幾乎和 96 題是一模一樣的炭菌。
注意：要寫一個(gè)輔助函數(shù)罪佳，拷貝一個(gè)二叉樹，有一定的偏移黑低。
# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def generateTrees(self, n):
"""
:type n: int
:rtype: List[TreeNode]
"""
if n <= 0:
return []
res = [None] * (n + 1)
res[0] = [None]
for i in range(1, n + 1):
# 初始化一個(gè)列表對象
res[i] = []
for j in range(i):
for left in res[j]:
for right in res[i - j - 1]:
# 注意：這里是 j + 1 赘艳，表示根結(jié)點(diǎn)，畫個(gè)圖就很清楚了
root = TreeNode(j + 1)
root.left = left
# 每個(gè)結(jié)點(diǎn)都有固定偏移的拷貝
root.right = self.__shift_clone(right, j + 1)
res[i].append(root)
return res[n]
def __shift_clone(self, root, k):
if root is None:
return root
cur_node = TreeNode(root.val + k)
cur_node.left = self.__shift_clone(root.left, k)
cur_node.right = self.__shift_clone(root.right, k)
return cur_node
LeetCode 第 94 題：二叉樹的中序遍歷
傳送門：https://leetcode.com/problems/binary-tree-inorder-traversal/description/。
遞歸寫法：
Java 代碼實(shí)現(xiàn)：
public class Solution2 {
private List<Integer> result = new ArrayList<>();
public List<Integer> inorderTraversal(TreeNode root) {
inorder(root);
return result;
}
private void inorder(TreeNode root) {
if (root != null) {
inorder(root.left);
result.add(root.val);
inorder(root.right);
}
}
}
非遞歸寫法
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
enum UseType {
RECURSION,
ADD
}
class Command {
UseType useType;
TreeNode treeNode;
Command(UseType useType, TreeNode treeNode) {
this.useType = useType;
this.treeNode = treeNode;
}
}
/**
* 什么是中序遍歷第练，先遞歸遍歷左子節(jié)點(diǎn)
* 在處理自己
* 然后再遞歸遍歷右子節(jié)點(diǎn)
*/
public class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
Stack<Command> stack = new Stack<>();
stack.push(new Command(UseType.RECURSION, root));
while (!stack.isEmpty()) {
Command command = stack.pop();
if (UseType.ADD == command.useType) {
result.add(command.treeNode.val);
} else {
assert UseType.RECURSION == command.useType;
if (command.treeNode.right != null) {
stack.push(new Command(UseType.RECURSION, command.treeNode.right));
}
stack.push(new Command(UseType.ADD, command.treeNode));
if (command.treeNode.left != null) {
stack.push(new Command(UseType.RECURSION, command.treeNode.left));
}
}
}
return result;
}
}
（本節(jié)完）
