104. 二叉树的最大深度
题目
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7回它的最大深度 3 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 题解
一棵二叉树要么是空树，要么有一个或两个指针，指针指向一棵树，
用递归实现很简单， 当指针为空，即是递归出口，返回0, 求最大深度就是左右子树选出一个最大值。
代码
func maxDepth(root *TreeNode) int {
if root == nil {
return 0
}
return int(math.Max(float64(maxDepth(root.Left)), float64(maxDepth(root.Right)))) + 1
} 110. 平衡二叉树
题目
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
示例 1:
给定二叉树 [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
返回 true 。
示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4]
1
/ \
2 2
/ \
3 3
/ \
4 4
返回 false 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/balanced-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 题解
首先知道二叉平衡树的性质，其是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
分两步走:
- 首先求左右子树的高度
- 判断左右子树的差值是否符合要求
代码
// 求二叉树的高度
func Height(node *TreeNode) (h int) {
if node == nil {
return 0
}
left := Height(node.Left)
right := Height(node.Right)
if left > right {
return left + 1
} else {
return right + 1
}
}
// 判断是否为二叉平衡树
func isBalanced(root *TreeNode) bool {
if root == nil {
return true
}
diff := Height(root.Left) - Height(root.Right)
if diff < -1 || diff > 1 {
return false
}
if isBalanced(root.Left) && isBalanced(root.Right) {
return true
}
return false
} 543. 二叉树的直径
题目
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。
示例 :
给定二叉树
1
/ \
2 3
/ \
4 5
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
注意：两结点之间的路径长度是以它们之间边的数目表示
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/diameter-of-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 题解
- 二叉树的直径等于从一个结点到另一个结点的最大长度，也就是左子树的最大深度+右子树的最大深度+1。
- 采用分治法和递归进行求解。
代码
var max int = 0
func diameterOfBinaryTree(root *TreeNode) int {
max = 0 // 运行样例前需要重置为0
Depth(root)
return max
}
// 最长路径
func Depth(node *TreeNode) int {
if node == nil {
return 0
}
left := Depth(node.Left)
right := Depth(node.Right)
if left + right > max {
max = left + right
}
if left > right {
return left + 1
} else {
return right + 1
}
} 226.翻转二叉树
题目
翻转一棵二叉树。
示例：
输入：
4
/ \
2 7
/ \ / \
1 3 6 9
输出：
4
/ \
7 2
/ \ / \
9 6 3 1
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/invert-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 题解
二叉树的翻转，其实就是递归的将左右子树进行调换。
代码
// 翻转二叉树
func invertTree(root *TreeNode) *TreeNode {
if root == nil {
return nil
}
// go语言特性交换值
root.Left, root.Right = root.Right, root.Left
invertTree(root.Left)
invertTree(root.Right)
return root
} 617.合并二叉树
题目
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
示例 1:
输入:
Tree 1 Tree 2
1 2
/ \ / \
3 2 1 3
/ \ \
5 4 7
输出:
合并后的树:
3
/ \
4 5
/ \ \
5 4 7
注意: 合并必须从两个树的根节点开始。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-two-binary-trees
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 题解
递归合并即可， 当两棵树都为空时即是递归出口，其中一棵树为空则用另一颗树填充，均不为空则将值相加作为新节点。
代码
// 合并二叉树
func mergeTrees(t1 *TreeNode, t2 *TreeNode) *TreeNode {
if t1 == nil && t2 == nil {
return nil
}
if t1 == nil {
return t2
}
if t2 == nil {
return t1
}
root := new(TreeNode)
root.Val = t1.Val + t2.Val
root.Left = mergeTrees(t1.Left, t2.Left) // 合并左子树
root.Right = mergeTrees(t1.Right, t2.Right) // 合并右子树
return root
} 112.路径总和
题目
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树，以及目标和 sum = 22，
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/path-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 题解
使用目标值一步进行递减， 每个结点都有两条路径可走，判断结点没有左右子结点时该结点即为终止结点，只需判断最终值是否跟sum的剩余值相等即可。
代码
// 判断路径和是否等于一个数
func hasPathSum(root *TreeNode, sum int) bool {
if root == nil {
return false
}
if root.Left == nil && root.Right == nil && root.Val == sum {
return true
}
return hasPathSum(root.Left, sum - root.Val) || hasPathSum(root.Right, sum - root.Val)
} 116. 路径总和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
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/path-sum-iii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 题解
进行双重递归, 根结点向下遍历, 根的左右结点再进行向下遍历。
代码
func pathSum(root *TreeNode, sum int) int {
if root == nil{
return 0
}
return pathSumRecursion(root, sum, 0) + pathSum(root.Left, sum) + pathSum(root.Right, sum)
}
func pathSumRecursion(root *TreeNode, sum int, count int)int{
if root == nil {
return count
}
sum -= root.Val
if sum == 0{
count++
}
count = pathSumRecursion(root.Left, sum, count)
count = pathSumRecursion(root.Right, sum, count)
return count
} 572.另一个树的子树
题目
给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。
示例 1:
给定的树 s:
3
/ \
4 5
/ \
1 2
给定的树 t：
4
/ \
1 2
返回 true，因为 t 与 s 的一个子树拥有相同的结构和节点值。
示例 2:
给定的树 s：
3
/ \
4 5
/ \
1 2
/
0
给定的树 t：
4
/ \
1 2
返回 false。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/subtree-of-another-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 题解
检测s中是否包含子树t，s自身拆分成多个树，与树t进行比较是否相等。
代码
// 判断是否有子树
func isSubtree(s *TreeNode, t *TreeNode) bool {
if s == nil {
return false
}
return isSame(s, t) || isSubtree(s.Left, t) || isSubtree(s.Right, t)
}
// 判断两树是否相同
func isSame(s *TreeNode, t *TreeNode) bool {
if s == nil && t == nil {
return true
}
if s == nil || t == nil {
return false
}
return s.Val == t.Val && isSame(s.Left, t.Left) && isSame(s.Right, t.Right)
} 101.对称二叉树
题目
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
1
/ \
2 2
/ \ / \
3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1
/ \
2 2
\ \
3 3
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/symmetric-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 题解
判断是否为对称二叉树， 跟判断两个树是否相同差不多， 只不过是将二叉树1的左子树跟二叉树2的右子树进行比较。
代码
// 判断是否为镜像树
func isSymmetric(root *TreeNode) bool {
if root == nil {
return true
}
return isSmt(root.Left, root.Right)
}
// 判断是否为镜像树
func isSmt(t1 *TreeNode, t2 *TreeNode) bool {
if t1 == nil && t2 == nil {
return true
}
if t1 == nil || t2 == nil {
return false
}
// t1的左子树跟t2的右子树进行对比
return (t1.Val == t2.Val) && isSmt(t1.Left, t2.Right) && isSmt(t1.Right, t2.Left)
} 111. 二叉树的最小深度
题目
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回它的最小深度 2.
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-depth-of-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 题解
思想跟求二叉树的最大深度类似， 区别在于数值的比较。
代码
func minDepth(root *TreeNode) int {
if root == nil {
return 0
}
left := minDepth(root.Left)
right := minDepth(root.Right)
if left == 0 || right == 0 {
return left + right + 1
}
if left < right {
return left + 1
}else {
return right + 1
}
} 404.左叶子之和
题目
计算给定二叉树的所有左叶子之和。
示例：
3
/ \
9 20
/ \
15 7
在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sum-of-left-leaves
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 题解
递归遍历结点，只添加左叶子结点的值。
代码
func sumOfLeftLeaves(root *TreeNode) int {
if root == nil {
return 0
}
if isLeaf(root.Left) { // 剪枝
return root.Left.Val + sumOfLeftLeaves(root.Right);
}
return sumOfLeftLeaves(root.Left) + sumOfLeftLeaves(root.Right)
}
// 判断结点是否有子节点, 用于剪枝
func isLeaf(node *TreeNode) bool {
if node == nil {
return false
}
return node.Left == nil && node.Right == nil
} 337.打家劫舍III
题目
在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。
计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。
示例 1:
输入: [3,2,3,null,3,null,1]
3
/ \
2 3
\ \
3 1
输出: 7
解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.
示例 2:
输入: [3,4,5,1,3,null,1]
3
/ \
4 5
/ \ \
1 3 1
输出: 9
解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/house-robber-iii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 题解
其实就是间隔遍历节点， 可分为两种情况递归求解:
- 打劫根节点，那么就不能打劫左右子树了，要打劫子孙辈的所有节点。
- 不打劫根节点， 那么打劫左右子树。
- 判断两种情况的哪个价值高。
代码
// 间隔遍历
func rob(root *TreeNode) int {
if root == nil {
return 0
}
val1 := root.Val
// 打劫子孙辈节点
if root.Left != nil {
val1 += rob(root.Left.Left) + rob(root.Left.Right)
}
if root.Right != nil {
val1 += rob(root.Right.Left) + rob(root.Right.Right)
}
// 打劫左右子树
val2 := rob(root.Left) + rob(root.Right)
if val1 > val2 {
return val1
}
return val2
} 671.二叉树中第二小节点
题目
给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为 2 或 0。如果一个节点有两个子节点的话，那么这个节点的值不大于它的子节点的值。
给出这样的一个二叉树，你需要输出所有节点中的第二小的值。如果第二小的值不存在的话，输出 -1 。
示例 1:
输入:
2
/ \
2 5
/ \
5 7
输出: 5
说明: 最小的值是 2 ，第二小的值是 5 。
示例 2:
输入:
2
/ \
2 2
输出: -1
说明: 最小的值是 2, 但是不存在第二小的值。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/second-minimum-node-in-a-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 题解
- 由题可知，二叉树的子节点大于或等于父节点, 如果相等的情况下，则需要继续往子节点查找，
否则进行左右节点的比较，返回较小的一个，如果其中一个节点为空，那么另一个节点即为要找的值。
代码
func findSecondMinimumValue(root *TreeNode) int {
if root == nil { //根节点为空，找不到
return -1
}
// 左右子树为空找不到
if root.Left == nil && root.Right == nil {
return -1
}
left := root.Left.Val
right := root.Right.Val
if left == root.Val { // 左子树与根节点值相同继续往下找
left = findSecondMinimumValue(root.Left)
}
if right == root.Val { // 右子树与根节点值相同继续往下找
right = findSecondMinimumValue(root.Right)
}
// 左右子树进行比较，返回值小的
if left != -1 && right != -1 {
return min(left, right)
}
// 左子树不为空，则返回左子树，否则为右子树
if left != -1 {
return left
}
return right
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
京公网安备 11010502036488号