首页 计算机科学 算法训练 2023

# 二叉树 DFS

# 算法题

# 双指针问题

# 1. 相同的树

https://leetcode.cn/problems/same-tree/description/

https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/08_BinaryTree/level_1/topic_1.go

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

func isSameTree(p *TreeNode, q *TreeNode) bool {
	if p == nil && q == nil {
		return true
	}
	if p == nil || q == nil {
		return false
	}
	if p.Val != q.Val {
		return false
	}
	return isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
}
# 2. 对称二叉树
https://leetcode.cn/problems/symmetric-tree/description/
https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/08_BinaryTree/level_1/topic_2.go
给你一个二叉树的根节点 root ， 检查它是否轴对称。
func isSymmetric(root *TreeNode) bool {
	if root == nil {
		return true
	}
	return subIsSymmetric(root.Left, root.Right)
}
func subIsSymmetric(node1, node2 *TreeNode) bool {
	if node1 == nil && node2 == nil {
		return true
	}
	if node1 == nil || node2 == nil {
		return false
	}
	if node1.Val != node2.Val {
		return false
	}
	return subIsSymmetric(node1.Left, node2.Right) && subIsSymmetric(node1.Right, node2.Left)
}
# 3. 合并二叉树
https://leetcode.cn/problems/merge-two-binary-trees/description/
https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/08_BinaryTree/level_1/topic_3.go
给你两棵二叉树： root1 和 root2 。
想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。
返回合并后的二叉树。
注意: 合并过程必须从两个树的根节点开始。
func mergeTrees(root1 *TreeNode, root2 *TreeNode) *TreeNode {
	if root1 == nil && root2 == nil {
		return root1
	}
	if root1 == nil && root2 != nil {
		return root2
	}
	if root1 != nil && root2 == nil {
		return root1
	}
	root1.Val += root2.Val
	root1.Right = mergeTrees(root1.Right, root2.Right)
	root1.Left = mergeTrees(root1.Left, root2.Left)
	return root1
}
# 路径问
# 4. 二叉树的所有路径
https://leetcode.cn/problems/binary-tree-paths/description/
https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/08_BinaryTree/level_1/topic_4.go
给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。
var pathList []string
func binaryTreePaths(root *TreeNode) []string {
	pathList = make([]string, 0)
	dfs(root, "")
	return pathList
}
func dfs(node *TreeNode, path string) {
	if node == nil {
		return
	}
	if node.Left == nil && node.Right == nil {
		pathList = append(pathList, path+strconv.Itoa(node.Val))
		return
	}
	dfs(node.Left, path+strconv.Itoa(node.Val)+"->")
	dfs(node.Right, path+strconv.Itoa(node.Val)+"->")
}
# 5. 二叉树的路径总和
https://leetcode.cn/problems/path-sum/
https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/08_BinaryTree/level_1/topic_5.go
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
叶子节点 是指没有子节点的节点。
func hasPathSum(root *TreeNode, targetSum int) bool {
	if root == nil {
		return false
	}
	if root.Left == nil && root.Right == nil {
		return root.Val-targetSum == 0
	}
	return hasPathSum(root.Left, targetSum-root.Val) || hasPathSum(root.Right, targetSum-root.Val)
}
# 深度和高度问题
# 6. 二叉树的最大深度
https://leetcode.cn/problems/maximum-depth-of-binary-tree/description/
https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/08_BinaryTree/level_2/topic_1.go
给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
func maxDepth(root *TreeNode) int {
	return subMaxDepth(root, 1)
}
func subMaxDepth(root *TreeNode, nowDepth int) int {
	if root == nil {
		return nowDepth - 1
	}
	if root.Left == nil && root.Right == nil {
		return nowDepth
	}
	return max(subMaxDepth(root.Right, nowDepth+1), subMaxDepth(root.Left, nowDepth+1))
}
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
# 7. 高度平衡二叉树
https://leetcode.cn/problems/balanced-binary-tree/
https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/08_BinaryTree/level_2/topic_2.go
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
func isBalanced(root *TreeNode) bool {
	return height(root) >= 0
}
func height(node *TreeNode) int {
	if node == nil {
		return 0
	}
	leftHight := height(node.Left)
	rightHight := height(node.Right)
	if leftHight == -1 || rightHight == -1 || abs(leftHight-rightHight) > 1 {
		return -1
	}
	return maxV2(leftHight, rightHight) + 1
}
func maxV2(a, b int) int {
	if a > b {
		return a
	}
	return b
}
func abs(x int) int {
	if x < 0 {
		return -1 * x
	}
	return x
}
# 8. 二叉树的最小深度
https://leetcode.cn/problems/minimum-depth-of-binary-tree/description/
https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/08_BinaryTree/level_2/topic_3.go
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
** 说明：** 叶子节点是指没有子节点的节点。
func minDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}
	if root.Left == nil && root.Right == nil {
		return 1
	}
	minDep := 10000
	if root.Left != nil {
		minDep = min(minDep, minDepth(root.Left))
	}
	if root.Right != nil {
		minDep = min(minDep, minDepth(root.Right))
	}
	return minDep + 1
}
func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}
# 9.N 叉树的最大深度
https://leetcode.cn/problems/maximum-depth-of-n-ary-tree/description/
https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/08_BinaryTree/level_2/topic_4.go
给定一个 N 叉树，找到其最大深度。
最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔
func maxDepth(root *Node) int {
	if root == nil {
		return 0
	}
	maxDep := 0
	for _, node := range root.Children {
		maxDep = max(maxDep, maxDepth(node))
	}
	return maxDep + 1
}
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
# 祖先问题
# 10. 二叉树的最近公共祖先
https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/
https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/08_BinaryTree/level_3/topic_1.go
给定一个二叉树，找到该树中两个指定节点的最近公共祖先。
最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	if root == nil {
		return root
	}
	// 如果当前节点为目标节点，则直接返回，不用判断底下节点，就算底下节点为目标节点，当前节点也是目标节点的公共祖先
	if root.Val == q.Val || root.Val == p.Val {
		return root
	}
	left := lowestCommonAncestor(root.Left, p, q)
	right := lowestCommonAncestor(root.Right, p, q)
	// 当前节点为公共祖先
	if left != nil && right != nil {
		return root
	}
	// 把公共祖先传到最外层
	if left != nil {
		return left
	}
	return right
}
 
-->