LeetCode 第 104 题：二叉树的最大深度
提示：思路1：后序遍历：看完左右子树，才能计算自己；
思路2：使用 BFS。
LeetCode 第 111题：二叉树的最小深度
提示：思路1：BFS 就可以做，并且我觉得思路更直接一些。并且求二叉树的最小深度也是这个套路。
思路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 题：反转一棵二叉树
image-20181214103339221
LeetCode 第 100 题：判断两个二叉树是否一样
image-20181214103315065
LeetCode 第 101 题：检查一棵树是否是镜像对称的
提示：首先理解什么是镜面对称。两个结点的根结点的值必须相等，并且1、左边的左结点=右边的右结点；2、左边的右结点=右边的左结点。我觉得没有什么技巧，记住就可以了。使用下面这张图思考这个问题。
思路1：递归。
image-20181214103655847
思路2：双端队列。
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
# 其实应该用 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 题：给出一个完全二叉树，求出该树的节点个数（典型递归问题）
提示：如果是满二叉树，结点的个数是有规律可循的。那么是不是满二叉树，可以通过子树的深度来判断。
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 题：是否是平衡二叉树
一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
Python 代码：使用后序遍历
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
# 给定一个二叉树，判断它是否是高度平衡的二叉树。
# 本题中，
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):
# 因为必须从底下到上面依次判断，所以使用后序遍历
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
# 重点，辅助函数的定义是，左右子树的高度中最大的那个
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
# 此时 root 不为空
# 左边看一看，右边看一看
# 【重点】一定要记得判断，左边子树和右边子树同时为空，说明走到底了
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 题：计算左边叶子结点数值之和
Python 代码：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# 关键在于判断是否是左边叶子结点
def sumOfLeftLeaves(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if root is None:
return 0
# 判断左边叶子结点是关键
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 题：得到二叉树的所有路径。
给定一个二叉树，返回所有从根节点到叶子节点的路径。
传送门：https://leetcode.com/problems/binary-tree-paths/description/
分析：典型的回溯。下面的这个写法比较奇怪。
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;
}
// 这个节点是个根节点，想一想只有一个元素的情况
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;
}
}
心得：分析递归关系是这道题的难点。
LeetCode 第 113 题：给定一棵二叉树，返回所有从根节点到叶子节点的路径，并且要等于指定的和
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)
# 这一步很关键
path.pop()
LeetCode 第 113 题：路径总和 II
要求：给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
说明: 叶子节点是指没有子节点的节点。
要特别注意弹出，即回溯的过程。
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;
}
// 根节点
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);
}
}
}
题后总结：使用递归的方法解决问题，很多时候，并不是让我们真正地去做这个问题，而是须要我们发现递归关系，寻找递归终止条件。历史上类似的经典问题有汉诺塔问题和八皇后问题。
但是，我自己觉得，我的解法，尤其是在 mergeOneAndList() 函数的部分稍显复杂。
下面给出一种简介的解法：这种解法显得更自然一些，遍历了从根节点到叶子节点的每一个节点，然后累加计算加到了多少，这是与老师的思路不同的一种思路。
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 {
// 什么都不做
// 在这里可以把不满足的节点都遍历出来
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 题：给定一棵二叉树，每个节点只包含数字 0-9，从根节点到叶子节点的每条路径可以表示成一个数，求这些数的和
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 中对于基础的数据类型是值传递，即复制
def __dfs(self, root, cum_sum, res):
if root is None:
return None
if root.left is None and root.right is None:
# 结算
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（重点，递归，二叉树典型处理思路）
提示：使用双重递归。
传送门：437. 路径总和 III。
给定一个二叉树，它的每个结点都存放着一个整数值。
找出路径和等于给定数值的路径总数。
路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。
示例：
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：模拟系统栈。
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 题 ：删除二叉搜索树中的节点（一定要会！）
LeetCode 第 108 题：将有序数组转换为二叉搜索树
LeetCode 第 230 题：二叉搜索树中第 K 小的元素
思路1：递归。
思路2：用模拟系统栈。
LeetCode 第 236 题：二叉树的最近公共祖先
LeetCode 第 297 题：二叉树的序列化与反序列化
传送门：二叉树的序列化与反序列化。同《剑指 Offer 》第 37 题。
使用前序遍历和中序遍历的结果还原一棵二叉树。
LeetCode 第 703 题：数据流中的第 k 大元素
下面的问题都来自 BST（二分搜索树）。
LeetCode 第 235 题：二分搜索树的最近公共祖先
LeetCode 第 450 题：删除一个二分搜索树的结点（必会，不难，多写几遍）
LeetCode 第 108 题：将有序数组转换为二叉搜索树
LeetCode 第 203 题：二叉搜索树中第 K 小的元素
LeetCode 第 236 题：二叉树的最近公共祖先
LeetCode 第 96 题：
要求：给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？
示例:
输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
分析：使用动态规划。
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];
// 想清楚这个值很关键
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
// 这里 j 表示左子树的元素个数，最小是 0 ，最大是 i-1
// 左边子树 + 右边子树 = i - 1
// i - j - 1 表示的是右边子树元素个数
for (int j = 0; j < i; j++) {
// 使用 * 是因为乘法计数原理
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
要求：给定一个整数 n，生成所有由 1 ... n 为节点所组成的二叉搜索树。
示例:
输入: 3
输出:
[
[1,null,3,2],
[3,2,null,1],
[3,1,null,null,2],
[2,1,3],
[1,null,2,null,3]
]
解释:
以上的输出对应以下 5 种不同结构的二叉搜索树：
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:
# 说明不构成区间，应该返回空结点
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
动态规划：这个解法几乎和 96 题是一模一样的。
注意：要写一个辅助函数，拷贝一个二叉树，有一定的偏移。
# 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):
# 初始化一个列表对象
res[i] = []
for j in range(i):
for left in res[j]:
for right in res[i - j - 1]:
# 注意：这里是 j + 1 ，表示根结点，画个图就很清楚了
root = TreeNode(j + 1)
root.left = left
# 每个结点都有固定偏移的拷贝
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 代码实现：
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;
}
}
/**
* 什么是中序遍历，先递归遍历左子节点
* 在处理自己
* 然后再递归遍历右子节点
*/
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;
}
}
（本节完）
网友评论