- 写二叉树的算法题，都是基于递归框架的，我们先要搞清楚
root节点它自己要做什么，然后根据题目要求选择使用前序，中序，后续的递归框架。 - 100. 相同的树">100. 相同的树
- 101. 对称二叉树">101. 对称二叉树
- 104. 二叉树的最大深度">104. 二叉树的最大深度
- 107. 二叉树的层次遍历 II">107. 二叉树的层次遍历 II
- 108. 将有序数组转换为二叉搜索树">108. 将有序数组转换为二叉搜索树
- 110. 平衡二叉树">110. 平衡二叉树
- 111. 二叉树的最小深度">111. 二叉树的最小深度
- 112. 路径总和">112. 路径总和
- 226. 翻转二叉树">226. 翻转二叉树
- 235. 二叉搜索树的最近公共祖先">235. 二叉搜索树的最近公共祖先
- 257. 二叉树的所有路径">257. 二叉树的所有路径
- 437. 路径总和 III">437. 路径总和 III
/* 二叉树遍历框架 */void traverse(TreeNode root) {// 前序遍历traverse(root.left)// 中序遍历traverse(root.right)// 后序遍历}
快排
快速排序的逻辑是，若要对 nums[lo..hi] 进行排序，我们先找一个分界点 p，通过交换元素使得 nums[lo..p-1] 都小于等于 nums[p]，且 nums[p+1..hi] 都大于 nums[p]，然后递归地去 nums[lo..p-1] 和 nums[p+1..hi] 中寻找新的分界点，最后整个数组就被排序了。
void sort(int[] nums, int lo, int hi) {
/****** 前序遍历位置 ******/
// 通过交换元素构建分界点 p
int p = partition(nums, lo, hi);
/************************/
sort(nums, lo, p - 1);
sort(nums, p + 1, hi);
}
再说说归并排序的逻辑，若要对 nums[lo..hi] 进行排序，我们先对 nums[lo..mid] 排序，再对 nums[mid+1..hi] 排序，最后把这两个有序的子数组合并，整个数组就排好序了
void sort(int[] nums, int lo, int hi) {
int mid = (lo + hi) / 2;
sort(nums, lo, mid);
sort(nums, mid + 1, hi);
/****** 后序遍历位置 ******/
// 合并两个排好序的子数组
merge(nums, lo, mid, hi);
/************************/
}
写二叉树的算法题，都是基于递归框架的，我们先要搞清楚 root 节点它自己要做什么，然后根据题目要求选择使用前序，中序，后续的递归框架。
100. 相同的树
给定两个二叉树，编写一个函数来检验它们是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例 :
输入: 1 1
/ \ / \
2 3 2 3
[1,2,3], [1,2,3]
输出: true
思路
二叉树的问题，通常通过递归的思想来解决。如果两棵树都是空树，返回True，如果两棵树都不是空，那么分别判断两棵树的根节点的数值，左结点和右结点是否相同。
代码
class Solution(object):
def isSameTree(self, p, q):
if p is None and q is None:
return True
if p is not None and q is not None:
return p.val==q.val and self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)
return False
101. 对称二叉树
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
1
/ \
2 2
/ \ / \
3 4 4 3
思路
这个题思路和100题有点类似，依然是递归的思想，首先判断头结点是否为空。然后将根节点的左右两个节点假设成两个独立的树，如果左右两个树都为空，返回True。然后看左子树的左结点和右子树的右结点、左子树的右结点和右子树的左结点是否相同，都相同返回True.
代码
class Solution(object):
def isSymmetric(self, root):
if root is None:
return True
return self.isSymmetricTree(root.left,root.right)
def isSymmetricTree(self,left,right):
if left is None and right is None:
return True
if left is None or right is None or left.val != right.val:
return False
return self.isSymmetricTree(left.left,right.right) and self.isSymmetricTree(left.right,right.left)
104. 二叉树的最大深度
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
示例：
给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
思路
递归的方法，比较左边路径和右边路径哪边最长，选择最长的一边路径，加上root结点本身的长度。
代码
class Solution(object):
def maxDepth(self, root):
if root is None:
return 0
else:
return max(self.maxDepth(root.left),self.maxDepth(root.right))+1
107. 二叉树的层次遍历 II
给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
例如：给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其自底向上的层次遍历为：
[
[15,7],
[9,20],
[3]
]
思路
一层层地输出result：[3],[9,20],[15,7]，然后翻转result [::-1]，返回[15,7],[9,20],[3]。如果不一层层输出，直接输出[3,9,20,15,7]，然后翻转变成了[7,15,20,9,3]。
代码
class Solution(object):
def levelOrderBottom(self, root):
if root is None:
return []
result,current = [],[root]
while current:
next_level,vals = [], []
for node in current:
vals.append(node.val)
if node.left:
next_level.append(node.left)
if node.right:
next_level.append(node.right)
current = next_level
result.append(vals)
return result[::-1]
108. 将有序数组转换为二叉搜索树
将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定有序数组: [-10,-3,0,5,9],
一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
0
/ \
-3 9
/ /
-10 5
思路
这也是个高频题，用递归的方法找到root结点，以及左子树和右子树。
代码
class Solution(object):
def sortedArrayToBST(self, nums):
"""
:type nums: List[int]
:rtype: TreeNode
"""
def to_bst(nums, start, end):
if start > end:
return None
mid = (start+end)//2
node = TreeNode(nums[mid])
node.left = to_bst(nums, start, mid-1)
node.right = to_bst(nums, mid+1,end)
return node
return to_bst(nums, 0, len(nums) - 1)
110. 平衡二叉树
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
示例 :
给定二叉树 [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
返回 true 。
思路
利用104题中判断二叉树最大深度的函数，左子树和右子树的深度差小于等于1即为平衡二叉树。
代码
class Solution(object):
def isBalanced(self, root):
if root == None:
return True
elif abs(self.height(root.left)-self.height(root.right))>1:
return False
else:
return self.isBalanced(root.left) and self.isBalanced(root.right)
def height(self,root):
if root == None:
return 0
else:
return max(self.height(root.left),self.height(root.right))+ 1
111. 二叉树的最小深度
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
示例:
给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回它的最小深度 2.
思路
如果根节点不存在，返回0；然后找根节点的左右子节点，找到深度最小的值，然后加1。
有一个特殊情况，如果根节点只有一个结点，那么深度最小的值不是1，具体见下例。因为是到最近的叶子节点的深度。
例： 3
\
4
/ \
5 6 这种情况下，最小深度不是1，而是3。
代码
class Solution(object):
def minDepth(self, root):
if root is None:
return 0
if root.left and root.right:
return min(self.minDepth(root.left),self.minDepth(root.right))+1
else:
return max(self.minDepth(root.left),self.minDepth(root.right))+1
112. 路径总和
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
示例:
给定如下二叉树，以及目标和 sum = 22，
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
思路
从上到下加起来，最后一个节点的值就等于sum-前面的和，且这个节点是叶子节点。
代码
class Solution(object):
def hasPathSum(self, root, sum):
if root is None:
return False
if root.left is None and root.right is None and root.val==sum:
return True
else:
return self.hasPathSum(root.left,sum-root.val) or self.hasPathSum(root.right,sum-root.val)
226. 翻转二叉树
翻转一棵二叉树。
我们发现只要把二叉树上的每一个节点的左右子节点进行交换，最后的结果就是完全翻转之后的二叉树。
这道题目比较简单，关键思路在于我们发现翻转整棵树就是交换每个节点的左右子节点，于是我们把交换左右子节点的代码放在了前序遍历的位置。
二叉树题目的一个难点就是，如何把题目的要求细化成每个节点需要做的事情。
// 将整棵树的节点翻转
TreeNode invertTree(TreeNode root) {
// base case
if (root == null) {
return null;
}
/**** 前序遍历位置 ****/
// root 节点需要交换它的左右子节点
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
// 让左右子节点继续翻转它们的子节点
invertTree(root.left);
invertTree(root.right);
return root;
}
示例：
输入：
4
/ \
2 7
/ \ / \
1 3 6 9
输出：
4
/ \
7 2
/ \ / \
9 6 3 1
思路
交换左右节点
代码
class Solution(object):
def invertTree(self, root):
if root is not None:
root.left,root.right = self.invertTree(root.right),self.invertTree(root.left)
return root
235. 二叉搜索树的最近公共祖先
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
示例 1: 输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8。输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。
示例 2: 输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4。 输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
思路
二叉搜索树（Binary Search Tree，BST），它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。
从上到下，如果这两个值都大于该节点，那么就往该节点的右节点继续查找；若都小于该节点，那么就往该节点的左节点继续查找，如果一个值等于该节点，那么该节点即为最近公共祖先。
代码
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def lowestCommonAncestor(self, root, p, q):
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
"""
pointer = root
while pointer:
if q.val < pointer.val and p.val < pointer.val:
pointer = pointer.left
elif q.val > pointer.val and p.val > pointer.val:
pointer = pointer.right
else:
return pointer
257. 二叉树的所有路径
给定一个二叉树，返回所有从根节点到叶子节点的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
输入:
1
/ \
2 3
\
5
输出: ["1->2->5", "1->3"]
解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3
代码
class Solution(object):
def binaryTreePaths(self, root):
"""
:type root: TreeNode
:rtype: List[str]
"""
result = list()
if root == None:
return result
if root.left == None and root.right == None:
result.append(str(root.val))
return result
left = self.binaryTreePaths(root.left)
for i in range(len(left)):
result.append(str(root.val) + '->' + left[i])
right = self.binaryTreePaths(root.right)
for i in range(len(right)):
result.append(str(root.val) + '->' + right[i])
return result
404. 左叶子之和
计算给定二叉树的所有左叶子之和。
示例：
3
/ \
9 20
/ \
15 7
在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24
代码
class Solution(object):
def sumOfLeftLeaves(self, root):
"""
:type root: TreeNode
:rtype: int
"""
result = 0
if not root:
return 0
if root.left and not root.left.left and not root.left.right:
result += root.left.val
return result+self.sumOfLeftLeaves(root.left)+self.sumOfLeftLeaves(root.right)
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
思路
借助一个函数：查找从该点出发得到目标值的路径的个数。
代码
class Solution(object):
def pathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: int
"""
if not root:
return 0
return self.pathSumFrom(root, sum) + self.pathSum(root.left, sum) + self.pathSum(root.right, sum)
def pathSumFrom(self, node, sum):
if not node:
return 0
return (1 if node.val == sum else 0) + self.pathSumFrom(node.left, sum - node.val) + self.pathSumFrom(node.right, sum - node.val)
若有收获，就点个赞吧
0 人点赞
