LeetCode Go · 树与二叉树（4）

来源与许可

题目版权归 LeetCode；题解来自 Doocs/leetcode，按 CC BY-SA 4.0 共享。补充 Go 代码来自灵茶山艾府、halfrost，保留 MIT 许可及逐题署名。本站提取 Go、调整分类及折叠排版；标注“本站整理”的 Go 解法依据题意与参考思路补写，按 CC BY-SA 4.0 共享。收录日期：2026-10-31；主题源版本：91ef8c241a5e。

本卷 30 题 · 点击题目展开，先独立思考，再查看解法。

814. 二叉树剪枝

中等1 种解法

标签：树、深度优先搜索、二叉树

题目、示例与约束

给你二叉树的根结点 root ，此外树的每个结点的值要么是 0 ，要么是 1 。

返回移除了所有不包含 1 的子树的原二叉树。

节点 node 的子树为 node 本身加上所有 node 的后代。

示例 1：

输入：root = [1,null,0,0,1]
输出：[1,null,0,null,1]
解释：
只有红色节点满足条件“所有不包含 1 的子树”。 右图为返回的答案。

示例 2：

输入：root = [1,0,1,0,0,0,1]
输出：[1,null,1,null,1]

示例 3：

输入：root = [1,1,0,1,1,0,1,0]
输出：[1,1,0,1,1,null,1]

提示：

树中节点的数目在范围 [1, 200] 内
Node.val 为 0 或 1

方法一：递归 · Go 实现

思考

需要删去所有不含 $1$ 的子树。自顶向下无法在见到子树之前判断，应先递归处理左右孩子，再根据子树是否已被清空决定当前结点是否保留。

后序返回后，若结点值为 $0$ 且左右皆空，则整棵子树可删。结点至多 $200$ 个，一次 DFS 即可。

我们首先判断当前节点是否为空，如果为空则直接返回空节点。

否则，我们递归地对左右子树进行剪枝，并将剪枝后的左右子树重新赋值给当前节点的左右子节点。然后判断当前节点的值是否为 0 且左右子节点都为空，如果是则返回空节点，否则返回当前节点。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 为二叉树的节点个数。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func pruneTree(root *TreeNode) *TreeNode {
	if root == nil {
		return nil
	}
	root.Left = pruneTree(root.Left)
	root.Right = pruneTree(root.Right)
	if root.Val == 0 && root.Left == nil && root.Right == nil {
		return nil
	}
	return root
}

力扣原题 · Doocs 题解来源

863. 二叉树中所有距离为 K 的结点

中等1 种解法

标签：树、深度优先搜索、广度优先搜索、哈希表、二叉树

题目、示例与约束

给定一个二叉树（具有根结点 root），一个目标结点 target ，和一个整数值 k ，返回到目标结点 target 距离为 k 的所有结点的值的数组。

答案可以以 任何顺序 返回。

示例 1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2
输出：[7,4,1]
解释：所求结点为与目标结点（值为 5）距离为 2 的结点，值分别为 7，4，以及 1

示例 2:

输入: root = [1], target = 1, k = 3
输出: []

提示:

节点数在 [1, 500] 范围内
0 <= Node.val <= 500
Node.val 中所有值不同
目标结点 target 是树上的结点。
0 <= k <= 1000

方法一：DFS + 哈希表 · Go 实现

思考

在二叉树中找与 $target$ 距离为 $k$ 的结点。只有向下的孩子指针时，无法走向父结点。结点至多 $500$ 个，可先建父指针再从 $target$ 向外走 $k$ 步。

第一次 DFS 记下每个结点的父亲，第二次从 $target$ 向左、右、父三向扩展，避开来路，深度为 $0$ 时收集结点。

我们先用 DFS 遍历整棵树，将每个节点的父节点保存到哈希表 $g$ 中。

接下来，我们再次用 DFS，从 $target$ 出发，向上向下搜索距离为 $k$ 的节点，添加到结果数组中。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 为二叉树的节点个数。

func distanceK(root *TreeNode, target *TreeNode, k int) []int {
	g := make(map[*TreeNode]*TreeNode)
	ans := []int{}

	var dfs func(node, fa *TreeNode)
	dfs = func(node, fa *TreeNode) {
		if node == nil {
			return
		}
		g[node] = fa
		dfs(node.Left, node)
		dfs(node.Right, node)
	}

	var dfs2 func(node, fa *TreeNode, k int)
	dfs2 = func(node, fa *TreeNode, k int) {
		if node == nil {
			return
		}
		if k == 0 {
			ans = append(ans, node.Val)
			return
		}
		for _, nxt := range []*TreeNode{node.Left, node.Right, g[node]} {
			if nxt != fa {
				dfs2(nxt, node, k-1)
			}
		}
	}

	dfs(root, nil)
	dfs2(target, nil, k)

	return ans
}

力扣原题 · Doocs 题解来源

865. 具有所有最深节点的最小子树

中等1 种解法

标签：树、深度优先搜索、广度优先搜索、哈希表、二叉树、最近公共祖先、树形 DP

题目、示例与约束

给定一个根为 root 的二叉树，每个节点的深度是 该节点到根的最短距离 。

返回包含原始树中所有 最深节点 的 最小子树 。

如果一个节点在 整个树 的任意节点之间具有最大的深度，则该节点是 最深的 。

一个节点的子树是该节点加上它的所有后代的集合。

示例 1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4]
输出：[2,7,4]
解释：
我们返回值为 2 的节点，在图中用黄色标记。
在图中用蓝色标记的是树的最深的节点。
注意，节点 5、3 和 2 包含树中最深的节点，但节点 2 的子树最小，因此我们返回它。

示例 2：

输入：root = [1]
输出：[1]
解释：根节点是树中最深的节点。

示例 3：

输入：root = [0,1,3,null,2]
输出：[2]
解释：树中最深的节点为 2 ，有效子树为节点 2、1 和 0 的子树，但节点 2 的子树最小。

提示：

树中节点的数量在 [1, 500] 范围内。
0 <= Node.val <= 500
每个节点的值都是 独一无二 的。

注意：本题与力扣 1123 重复：https://leetcode.cn/problems/lowest-common-ancestor-of-deepest-leaves

方法一：递归 · Go 实现

思考

要包含全部最深叶的最小子树，即这些叶的最近公共祖先。先求深度再找 LCA 需要两遍；一次后序即可同时返回「候选根」与深度。

左右深度不等则答案在更深一侧；相等则当前结点正好盖住两侧最深叶。空结点深度为 $0$ 。

我们设计一个函数 $dfs (root)$ ，返回以 $root$ 为根的子树中，包含所有最深节点的最小子树，以及以 $root$ 为根的子树的深度。

函数 $dfs (root)$ 的执行过程如下：

如果 $root$ 为空，返回 $null$ 和 $0$ 。
否则，递归计算 $root$ 的左子树和右子树的最小子树以及深度，分别为 $l$ 和 $l_{d}$ 以及 $r$ 和 $r_{d}$ 。如果 $l_{d} > r_{d}$ ，则以 $root$ 的左孩子为根的子树中包含所有最深节点的最小子树就是 $l$ ，深度为 $l_{d} + 1$ ；如果 $l_{d} < r_{d}$ ，则以 $root$ 的右孩子为根的子树中包含所有最深节点的最小子树就是 $r$ ，深度为 $r_{d} + 1$ ；如果 $l_{d} = r_{d}$ ，则 $root$ 就是包含所有最深节点的最小子树，深度为 $l_{d} + 1$ 。

最后，返回 $dfs (root)$ 的结果的第一个元素即可。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 为二叉树的节点个数。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func subtreeWithAllDeepest(root *TreeNode) *TreeNode {
	type pair struct {
		node  *TreeNode
		depth int
	}
	var dfs func(*TreeNode) pair
	dfs = func(root *TreeNode) pair {
		if root == nil {
			return pair{nil, 0}
		}
		l, r := dfs(root.Left), dfs(root.Right)
		ld, rd := l.depth, r.depth
		if ld > rd {
			return pair{l.node, ld + 1}
		}
		if ld < rd {
			return pair{r.node, rd + 1}
		}
		return pair{root, ld + 1}
	}
	return dfs(root).node
}

力扣原题 · Doocs 题解来源

872. 叶子相似的树

简单1 种解法

标签：树、深度优先搜索、二叉树

题目、示例与约束

请考虑一棵二叉树上所有的叶子，这些叶子的值按从左到右的顺序排列形成一个 叶值序列 。

举个例子，如上图所示，给定一棵叶值序列为 (6, 7, 4, 9, 8) 的树。

如果有两棵二叉树的叶值序列是相同，那么我们就认为它们是 叶相似 的。

如果给定的两个根结点分别为 root1 和 root2 的树是叶相似的，则返回 true；否则返回 false 。

示例 1：

输入：root1 = [3,5,1,6,2,9,8,null,null,7,4], root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]
输出：true

示例 2：

输入：root1 = [1,2,3], root2 = [1,3,2]
输出：false

提示：

给定的两棵树结点数在 [1, 200] 范围内
给定的两棵树上的值在 [0, 200] 范围内

方法一：DFS · Go 实现

思考

比较两棵树从左到右的叶值序列。树很小，分别 DFS 收集叶子再比较即可。

左右皆空视为叶子。两棵树各收集一次，序列相等则为相似。

我们可以使用深度优先搜索来遍历两棵树的叶子节点，分别将叶子节点的值存储在两个列表 $l_{1}$ 和 $l_{2}$ 中，最后比较两个列表是否相等。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 为树的节点数。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func leafSimilar(root1 *TreeNode, root2 *TreeNode) bool {
	l1, l2 := []int{}, []int{}
	var dfs func(*TreeNode, *[]int)
	dfs = func(root *TreeNode, nums *[]int) {
		if root.Left == root.Right {
			*nums = append(*nums, root.Val)
			return
		}
		if root.Left != nil {
			dfs(root.Left, nums)
		}
		if root.Right != nil {
			dfs(root.Right, nums)
		}
	}
	dfs(root1, &l1)
	dfs(root2, &l2)
	return reflect.DeepEqual(l1, l2)
}

力扣原题 · Doocs 题解来源

889. 从前序与后序遍历序列构造二叉树

中等2 种解法

标签：树、数组、哈希表、分治、二叉树

题目、示例与约束

给定两个整数数组，preorder 和 postorder ，其中 preorder 是一个具有 无重复 值的二叉树的前序遍历，postorder 是同一棵树的后序遍历，重构并返回二叉树。

如果存在多个答案，您可以返回其中任何一个。

示例 1：

输入：preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]
输出：[1,2,3,4,5,6,7]

示例 2:

输入: preorder = [1], postorder = [1]
输出: [1]

提示：

1 <= preorder.length <= 30
1 <= preorder[i] <= preorder.length
preorder 中所有值都不同
postorder.length == preorder.length
1 <= postorder[i] <= postorder.length
postorder 中所有值都不同
保证 preorder 和 postorder 是同一棵二叉树的前序遍历和后序遍历

方法一：递归 · Go 实现

思考

前序与后序可确定一棵二叉树（题目保证唯一）。前序下一元素是左子根，它在后序中的位置划出左子区间。结点数 $\leq 30$ ，递归分治即可。

预处理后序值到下标。每次用左子根切出左右区间，再递归左右子树。单结点或空区间直接返回。

前序遍历的顺序是：根节点 -> 左子树 -> 右子树，后序遍历的顺序是：左子树 -> 右子树 -> 根节点。

因此，二叉树的根节点一定是前序遍历的第一个节点，也是后序遍历的最后一个节点。

接下来，我们需要确定二叉树的左子树范围和右子树范围。

如果二叉树有左子树，那么左子树的根节点一定是前序遍历的第二个节点；如果二叉树没有左子树，那么前序遍历的第二个节点一定是右子树的根节点。由于这两种情况下，后序遍历的结果是一样的，因此，我们可以把前序遍历的第二个节点作为左子树的根节点，然后找到它在后序遍历中的位置，这样就确定了左子树的范围。

具体地，我们设计一个递归函数 $d f s (a, b, c, d)$ ，其中 $[a, b]$ 表示前序遍历的范围，而 $[c, d]$ 表示后序遍历的范围。这个函数的功能是根据前序遍历 $[a, b]$ 和后序遍历 $[c, d]$ 构造出二叉树的根节点。那么答案就是 $d f s (0, n - 1, 0, n - 1)$ ，其中 $n$ 是前序遍历的长度。

函数 $d f s (a, b, c, d)$ 的执行步骤如下：

如果 $a > b$ ，说明范围为空，直接返回空节点。
否则，我们构造一个新的节点 $r o o t$ ，它的值为前序遍历中的第一个节点的值，也就是 $p r e o r d e r [a]$ 。
如果 $a$ 等于 $b$ ，说明 $r o o t$ 没有左子树也没有右子树，直接返回 $r o o t$ 。
否则，左子树的根节点的值为 $p r e o r d e r [a + 1]$ ，我们在后序遍历中找到 $p r e o r d e r [a + 1]$ 的位置，记为 $i$ 。那么左子树的节点个数 $m = i - c + 1$ ，由此可知左子树在前序遍历中的范围是 $[a + 1, a + m]$ ，后序遍历中的范围是 $[c, i]$ ，右子树在前序遍历中的范围是 $[a + m + 1, b]$ ，后序遍历中的范围是 $[i + 1, d - 1]$ 。
知道了左右子树的范围，我们就可以递归地重建左右子树，然后将左右子树的根节点分别作为 $r o o t$ 的左右子节点。最后返回 $r o o t$ 。

在函数 $d f s (a, b, c, d)$ 中，我们需要用到一个哈希表 $p o s$ ，它存储了后序遍历中每个节点的位置。在函数的开头，我们可以先计算出这个哈希表，这样就可以在 $O (1)$ 的时间内找到任意节点在后序遍历中的位置。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 是节点数。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func constructFromPrePost(preorder []int, postorder []int) *TreeNode {
	pos := map[int]int{}
	for i, x := range postorder {
		pos[x] = i
	}
	var dfs func(int, int, int, int) *TreeNode
	dfs = func(a, b, c, d int) *TreeNode {
		if a > b {
			return nil
		}
		root := &TreeNode{Val: preorder[a]}
		if a == b {
			return root
		}
		i := pos[preorder[a+1]]
		m := i - c + 1
		root.Left = dfs(a+1, a+m, c, i)
		root.Right = dfs(a+m+1, b, i+1, d-1)
		return root
	}
	return dfs(0, len(preorder)-1, 0, len(postorder)-1)
}

方法二：递归的另一种写法 · Go 实现

思考

方法一用四个端点描述两段区间。也可改成「前序起点、后序起点、结点个数」三个参数，左子大小仍由后序中左子根的位置算出。

递归结构不变，只是区间表示更紧，右子从 $i + m + 1$ 、 $k + 1$ 开始、长度为 $n - m - 1$ 。

我们也可以设计一个递归函数 $d f s (i, j, n)$ ，其中 $i$ 和 $j$ 表示前序遍历和后序遍历的起点，而 $n$ 表示节点个数。这个函数的功能是根据前序遍历 $[i, i + n - 1]$ 和后序遍历 $[j, j + n - 1]$ 构造出二叉树的根节点。那么答案就是 $d f s (0, 0, n)$ ，其中 $n$ 是前序遍历的长度。

函数 $d f s (i, j, n)$ 的执行步骤如下：

如果 $n = 0$ ，说明范围为空，直接返回空节点。
否则，我们构造一个新的节点 $r o o t$ ，它的值为前序遍历中的第一个节点的值，也就是 $p r e o r d e r [i]$ 。
如果 $n = 1$ ，说明 $r o o t$ 没有左子树也没有右子树，直接返回 $r o o t$ 。
否则，左子树的根节点的值为 $p r e o r d e r [i + 1]$ ，我们在后序遍历中找到 $p r e o r d e r [i + 1]$ 的位置，记为 $k$ 。那么左子树的节点个数 $m = k - j + 1$ ，右子树的节点数为 $n - m - 1$ 。我们递归地重建左右子树，然后将左右子树的根节点分别作为 $r o o t$ 的左右子节点。最后返回 $r o o t$ 。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 是节点数。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func constructFromPrePost(preorder []int, postorder []int) *TreeNode {
	pos := map[int]int{}
	for i, x := range postorder {
		pos[x] = i
	}
	var dfs func(int, int, int) *TreeNode
	dfs = func(i, j, n int) *TreeNode {
		if n <= 0 {
			return nil
		}
		root := &TreeNode{Val: preorder[i]}
		if n == 1 {
			return root
		}
		k := pos[preorder[i+1]]
		m := k - j + 1
		root.Left = dfs(i+1, j, m)
		root.Right = dfs(i+m+1, k+1, n-m-1)
		return root
	}
	return dfs(0, 0, len(preorder))
}

力扣原题 · Doocs 题解来源

894. 所有可能的真二叉树

中等1 种解法

标签：树、递归、记忆化、动态规划、二叉树

题目、示例与约束

给你一个整数 n ，请你找出所有可能含 n 个节点的 真二叉树 ，并以列表形式返回。答案中每棵树的每个节点都必须符合 Node.val == 0 。

答案的每个元素都是一棵真二叉树的根节点。你可以按 任意顺序 返回最终的真二叉树列表。

真二叉树 是一类二叉树，树中每个节点恰好有 0 或 2 个子节点。

示例 1：

输入：n = 7
输出：[[0,0,0,null,null,0,0,null,null,0,0],[0,0,0,null,null,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,null,null,null,null,0,0],[0,0,0,0,0,null,null,0,0]]

示例 2：

输入：n = 3
输出：[[0,0,0]]

提示：

1 <= n <= 20

方法一：记忆化搜索 · Go 实现

思考

满二叉树每个结点有 $0$ 或 $2$ 个孩子，结点数 $n \leq 20$ 。偶数个结点无法构成，奇数时可枚举左子结点个数。

记忆化 $d f s (n)$ ：根占一个，剩余 $n - 1$ 分给左右。对每对左右子树的笛卡尔积挂到新根上。 $n = 1$ 只有单结点。

如果 $n = 1$ ，直接返回单个节点的列表。

如果 $n > 1$ ，我们可以枚举左子树的节点数量 $i$ ，那么右子树的节点数量为 $n - 1 - i$ 。对于每种情况，我们递归地构造左子树和右子树的所有可能的真二叉树。然后将左子树和右子树两两组合，得到所有可能的真二叉树。

此过程可以用记忆化搜索，避免重复计算。

时间复杂度 $O (\frac{2^{n}}{\sqrt{n}})$ ，空间复杂度 $O (\frac{2^{n}}{\sqrt{n}})$ 。其中 $n$ 是节点数量。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func allPossibleFBT(n int) []*TreeNode {
	f := make([][]*TreeNode, n+1)
	var dfs func(int) []*TreeNode
	dfs = func(n int) []*TreeNode {
		if len(f[n]) > 0 {
			return f[n]
		}
		if n == 1 {
			return []*TreeNode{&TreeNode{Val: 0}}
		}
		ans := []*TreeNode{}
		for i := 0; i < n-1; i++ {
			j := n - 1 - i
			for _, left := range dfs(i) {
				for _, right := range dfs(j) {
					ans = append(ans, &TreeNode{0, left, right})
				}
			}
		}
		f[n] = ans
		return ans
	}
	return dfs(n)
}

力扣原题 · Doocs 题解来源

897. 递增顺序搜索树

简单1 种解法

标签：栈、树、深度优先搜索、二叉搜索树、二叉树

题目、示例与约束

给你一棵二叉搜索树的 root ，请你 按中序遍历 将其重新排列为一棵递增顺序搜索树，使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。

示例 1：

输入：root = [5,3,6,2,4,null,8,1,null,null,null,7,9]
输出：[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

示例 2：

输入：root = [5,1,7]
输出：[1,null,5,null,7]

提示：

树中节点数的取值范围是 [1, 100]
0 <= Node.val <= 1000

方法一：DFS 中序遍历 · Go 实现

思考

把二叉搜索树展成只有右孩子的递增链。中序恰好是递增序，结点至多 $100$ 个，中序时改指针即可，不必先收集再重建。

哑结点接在链头，访问到一个结点就接到 $prev$ 右侧并清空左孩子，再继续中序。最后返回哑结点的右孩子。

我们定义一个虚拟节点 $d u m m y$ ，初始时 $d u m m y$ 的右子节点指向根节点 $r o o t$ ，定义一个指针 $p r e v$ 指向 $d u m m y$ 。

我们对二叉搜索树进行中序遍历，遍历过程中，每遍历到一个节点，就将 $p r e v$ 的右子节点指向它，然后将当前节点的左子节点置为空，再将当前节点赋值给 $p r e v$ ，以便于下一次遍历。

遍历结束后，原二叉搜索树被修改成只有右子节点的单链表，我们再将虚拟节点 $d u m m y$ 的右子节点返回即可。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 为二叉搜索树的节点个数。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func increasingBST(root *TreeNode) *TreeNode {
	dummy := &TreeNode{Val: 0, Right: root}
	prev := dummy
	var dfs func(root *TreeNode)
	dfs = func(root *TreeNode) {
		if root == nil {
			return
		}
		dfs(root.Left)
		prev.Right = root
		root.Left = nil
		prev = root
		dfs(root.Right)
	}
	dfs(root)
	return dummy.Right
}

力扣原题 · Doocs 题解来源

938. 二叉搜索树的范围和

简单1 种解法

标签：树、深度优先搜索、二叉搜索树、二叉树

题目、示例与约束

给定二叉搜索树的根结点 root，返回值位于范围 [low, high] 之间的所有结点的值的和。

示例 1：

输入：root = [10,5,15,3,7,null,18], low = 7, high = 15
输出：32

示例 2：

输入：root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
输出：23

提示：

树中节点数目在范围 [1, 2 * 10⁴] 内
1 <= Node.val <= 10⁵
1 <= low <= high <= 10⁵
所有 Node.val 互不相同

方法一：DFS · Go 实现

思考

求 BST 中落在 $[l o w, h i g h]$ 的结点值和。中序遍历整棵树可行，但可用有序性剪枝：当前值已 $\leq l o w$ 则左子树不必看，已 $\geq h i g h$ 则右子树不必看。递归累加落在区间内的结点。

我们设计一个函数 $d f s (r o o t)$ ，表示求以 $r o o t$ 为根的子树中，值位于范围 $[l o w, h i g h]$ 之间的所有结点的值的和。那么答案就是 $d f s (r o o t)$ 。

函数 $d f s (r o o t)$ 的执行逻辑如下：

如果 $r o o t$ 为空，返回 $0$ 。
如果 $r o o t$ 的值 $x$ 在范围 $[l o w, h i g h]$ 之间，那么函数 $d f s (r o o t)$ 的初始答案就是 $x$ ，否则为 $0$ 。
如果 $x > l o w$ ，说明 $r o o t$ 的左子树中可能有值在范围 $[l o w, h i g h]$ 之间的结点，所以我们需要递归调用 $d f s (r o o t . l e f t)$ ，并将结果加到答案上。
如果 $x < h i g h$ ，说明 $r o o t$ 的右子树中可能有值在范围 $[l o w, h i g h]$ 之间的结点，所以我们需要递归调用 $d f s (r o o t . r i g h t)$ ，并将结果加到答案上。
最后返回答案。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 是二叉搜索树的结点个数。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func rangeSumBST(root *TreeNode, low int, high int) int {
	var dfs func(*TreeNode) int
	dfs = func(root *TreeNode) (ans int) {
		if root == nil {
			return 0
		}
		x := root.Val
		if low <= x && x <= high {
			ans += x
		}
		if x > low {
			ans += dfs(root.Left)
		}
		if x < high {
			ans += dfs(root.Right)
		}
		return
	}
	return dfs(root)
}

力扣原题 · Doocs 题解来源

951. 翻转等价二叉树

中等1 种解法

标签：树、深度优先搜索、二叉树

题目、示例与约束

我们可以为二叉树 T 定义一个 翻转操作 ，如下所示：选择任意节点，然后交换它的左子树和右子树。

只要经过一定次数的翻转操作后，能使 X 等于 Y，我们就称二叉树 X 翻转等价 于二叉树 Y。

这些树由根节点 root1 和 root2 给出。如果两个二叉树是翻转等价 的树，则返回 true ，否则返回 false 。

示例 1：

输入：root1 = [1,2,3,4,5,6,null,null,null,7,8], root2 = [1,3,2,null,6,4,5,null,null,null,null,8,7]
输出：true
解释：我们翻转值为 1，3 以及 5 的三个节点。

示例 2:

输入: root1 = [], root2 = []
输出: true

示例 3:

输入: root1 = [], root2 = [1]
输出: false

提示：

每棵树节点数在 [0, 100] 范围内
每棵树中的每个值都是唯一的、在 [0, 99] 范围内的整数

方法一 · Go 实现

思考

判断两棵树能否通过翻转左右孩子变得相同。结点值唯一，规模不超过 $100$ 。根值必须相同；翻转只发生在某一结点的两个孩子之间，因此递归时允许“不翻”或“对调后再比”，两支有一支成立即可。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func flipEquiv(root1 *TreeNode, root2 *TreeNode) bool {
	var dfs func(root1, root2 *TreeNode) bool
	dfs = func(root1, root2 *TreeNode) bool {
		if root1 == root2 || (root1 == nil && root2 == nil) {
			return true
		}
		if root1 == nil || root2 == nil || root1.Val != root2.Val {
			return false
		}
		return (dfs(root1.Left, root2.Left) && dfs(root1.Right, root2.Right)) || (dfs(root1.Left, root2.Right) && dfs(root1.Right, root2.Left))
	}
	return dfs(root1, root2)
}

力扣原题 · Doocs 题解来源

958. 二叉树的完全性检验

中等1 种解法

标签：树、广度优先搜索、二叉树

题目、示例与约束

给你一棵二叉树的根节点 root ，请你判断这棵树是否是一棵 完全二叉树 。

在一棵 完全二叉树 中，除了最后一层外，所有层都被完全填满，并且最后一层中的所有节点都尽可能靠左。最后一层（第 h 层）中可以包含 1 到 2^h 个节点。

示例 1：

输入：root = [1,2,3,4,5,6]
输出：true
解释：最后一层前的每一层都是满的（即，节点值为 {1} 和 {2,3} 的两层），且最后一层中的所有节点（{4,5,6}）尽可能靠左。

示例 2：

输入：root = [1,2,3,4,5,null,7]
输出：false
解释：值为 7 的节点不满足条件「节点尽可能靠左」。

提示：

树中节点数目在范围 [1, 100] 内
1 <= Node.val <= 1000

方法一 · Go 实现

思考

完全二叉树在层序中空结点之后不能再出现非空结点。层序入队时把空孩子也放入；一旦弹出空结点，队列里剩下的必须全空。结点不超过 $100$ ，一次 BFS 即可。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isCompleteTree(root *TreeNode) bool {
	q := []*TreeNode{root}
	for q[0] != nil {
		root = q[0]
		q = q[1:]
		q = append(q, root.Left)
		q = append(q, root.Right)
	}
	for len(q) > 0 && q[0] == nil {
		q = q[1:]
	}
	return len(q) == 0
}

力扣原题 · Doocs 题解来源

965. 单值二叉树

简单1 种解法

标签：树、深度优先搜索、广度优先搜索、二叉树

题目、示例与约束

如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。

只有给定的树是单值二叉树时，才返回 true；否则返回 false。

示例 1：

输入：[1,1,1,1,1,null,1]
输出：true

示例 2：

输入：[2,2,2,5,2]
输出：false

提示：

给定树的节点数范围是 [1, 100]。
每个节点的值都是整数，范围为 [0, 99] 。

方法一：DFS · Go 实现

思考

判断整棵树结点值是否全相同。记下根值 $x$ ，DFS 要求每个结点都等于 $x$ ，空结点视为成立。

我们记根节点的值为 $x$ ，然后设计一个函数 $dfs (root)$ ，它表示当前节点的值是否等于 $x$ ，并且它的左右子树也是单值二叉树。

在函数 $dfs (root)$ 中，如果当前节点为空，那么返回 $true$ ，否则，如果当前节点的值等于 $x$ ，并且它的左右子树也是单值二叉树，那么返回 $true$ ，否则返回 $false$ 。

在主函数中，我们调用 $dfs (root)$ ，并返回结果。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 是树中的节点数目。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isUnivalTree(root *TreeNode) bool {
	x := root.Val
	var dfs func(*TreeNode) bool
	dfs = func(root *TreeNode) bool {
		if root == nil {
			return true
		}
		return root.Val == x && dfs(root.Left) && dfs(root.Right)
	}
	return dfs(root)
}

力扣原题 · Doocs 题解来源

968. 监控二叉树

困难2 种解法

标签：树、深度优先搜索、动态规划、二叉树、树形 DP

题目、示例与约束

给定一个二叉树，我们在树的节点上安装摄像头。

节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。

计算监控树的所有节点所需的最小摄像头数量。

示例 1：

输入：[0,0,null,0,0]
输出：1
解释：如图所示，一台摄像头足以监控所有节点。

示例 2：

输入：[0,0,null,0,null,0,null,null,0]
输出：2
解释：需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。

提示：

给定树的节点数的范围是 [1, 1000]。
每个节点的值都是 0。

方法一：动态规划（树形 DP） · Go 实现

思考

摄像头覆盖自身、父与子，求最少个数。每个结点的最优依赖于子树状态，需区分“本结点有摄像头 / 被子覆盖 / 未被覆盖”。树形 DP 自底向上返回三种最小值，根不能处于未被覆盖状态。

对于每个节点，我们定义三种状态：

a：当前节点有摄像头
b：当前节点无摄像头，但被子节点监控
c：当前节点无摄像头，也没被子节点监控

接下来，我们设计一个函数 $d f s (r o o t)$ ，它将返回一个长度为 3 的数组，表示以 root 为根的子树中，三种状态下的最小摄像头数量。那么答案就是 $min (d f s (r o o t) [0], d f s (r o o t) [1])$ 。

函数 $d f s (r o o t)$ 的计算过程如下：

如果 root 为空，则返回 $[i n f, 0, 0]$ ，其中 inf 表示一个很大的数，它用于表示不可能的情况。

否则，我们递归计算 root 的左右子树，分别得到 $[l a, l b, l c]$ 和 $[r a, r b, r c]$ 。

如果当前节点有摄像头，那么它的左右节点必须都是被监控的状态，即 $a = min (l a, l b, l c) + min (r a, r b, r c) + 1$ 。
如果当前节点无摄像头，但被子节点监控，那么子节点可以是其中之一或者两个都有摄像头，即 $b = min (l a + r b, l b + r a, l a + r a)$ 。
如果当前节点无摄像头，也没被子节点监控，那么子节点必须被其子节点监控，即 $c = l b + r b$ 。

最后，我们返回 $[a, b, c]$ 。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 是二叉树的节点数。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func minCameraCover(root *TreeNode) int {
	var dfs func(*TreeNode) (int, int, int)
	dfs = func(root *TreeNode) (int, int, int) {
		if root == nil {
			return 1 << 29, 0, 0
		}
		la, lb, lc := dfs(root.Left)
		ra, rb, rc := dfs(root.Right)
		a := 1 + min(la, min(lb, lc)) + min(ra, min(rb, rc))
		b := min(la+ra, min(la+rb, lb+ra))
		c := lb + rb
		return a, b, c
	}
	a, b, _ := dfs(root)
	return min(a, b)
}

方法二：显式栈上的树形 DP · Go 实现

思考

摄像头覆盖自身、父结点与子结点，最少个数取决于每个结点怎么放置。自底向上区分三种状态：本结点有摄像头、被子结点覆盖、未被覆盖。在较短的树上，递归返回这三种最小值，根不能停在未被覆盖的状态。

结点个数可达 $1000$ 。左链使这次后序遍历按结点个数递归，调用栈会溢出。

每个结点的三种状态只由左右子树的三种状态决定，所以必须先处理孩子，再处理父亲。

因此用显式栈做后序遍历。进入结点时压入退出标记和左右孩子，退出时按原来的三个式子写入该结点的状态。根的答案取前两个状态的较小值。

对于每个节点，我们定义三种状态：

a：当前节点有摄像头
b：当前节点无摄像头，但被子节点监控
c：当前节点无摄像头，也没被子节点监控

空结点对应 $(i n f, 0, 0)$ ，其中 $i n f$ 是一个很大的数，表示不可能的情况。

我们用显式栈对二叉树做后序遍历。进入结点时压入退出标记，再压入右孩子和左孩子；退出时，左右子树的状态已经记下，记为 $[l a, l b, l c]$ 和 $[r a, r b, r c]$ 。

如果当前节点有摄像头，那么它的左右节点必须都是被监控的状态，即 $a = min (l a, l b, l c) + min (r a, r b, r c) + 1$ 。
如果当前节点无摄像头，但被子节点监控，那么子节点可以是其中之一或者两个都有摄像头，即 $b = min (l a + r b, l b + r a, l a + r a)$ 。
如果当前节点无摄像头，也没被子节点监控，那么子节点必须被其子节点监控，即 $c = l b + r b$ 。

根结点不能处于未被覆盖的状态，答案是 $min (a, b)$ 。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 是二叉树的节点数。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func minCameraCover(root *TreeNode) int {
	if root == nil {
		return 0
	}
	const inf = 1 << 29
	sub := map[*TreeNode][3]int{}
	type frame struct {
		node  *TreeNode
		state int
	}
	stk := []frame{{root, 0}}
	for len(stk) > 0 {
		cur := stk[len(stk)-1]
		stk = stk[:len(stk)-1]
		node := cur.node
		if cur.state == 0 {
			stk = append(stk, frame{node, 1})
			if node.Right != nil {
				stk = append(stk, frame{node.Right, 0})
			}
			if node.Left != nil {
				stk = append(stk, frame{node.Left, 0})
			}
			continue
		}
		l := [3]int{inf, 0, 0}
		r := [3]int{inf, 0, 0}
		if node.Left != nil {
			l = sub[node.Left]
		}
		if node.Right != nil {
			r = sub[node.Right]
		}
		a := 1 + min(l[0], min(l[1], l[2])) + min(r[0], min(r[1], r[2]))
		b := min(l[0]+r[0], min(l[0]+r[1], l[1]+r[0]))
		c := l[1] + r[1]
		sub[node] = [3]int{a, b, c}
	}
	ans := sub[root]
	return min(ans[0], ans[1])
}

力扣原题 · Doocs 题解来源

971. 翻转二叉树以匹配先序遍历

中等1 种解法

标签：树、深度优先搜索、二叉树

题目、示例与约束

给你一棵二叉树的根节点 root ，树中有 n 个节点，每个节点都有一个不同于其他节点且处于 1 到 n 之间的值。

另给你一个由 n 个值组成的行程序列 voyage ，表示预期的二叉树 先序遍历 结果。

通过交换节点的左右子树，可以翻转该二叉树中的任意节点。例，翻转节点 1 的效果如下：

请翻转最少的树中节点，使二叉树的 先序遍历 与预期的遍历行程 voyage 相匹配 。

如果可以，则返回 翻转的 所有节点的值的列表。你可以按任何顺序返回答案。如果不能，则返回列表 [-1]。

示例 1：

输入：root = [1,2], voyage = [2,1]
输出：[-1]
解释：翻转节点无法令先序遍历匹配预期行程。

示例 2：

输入：root = [1,2,3], voyage = [1,3,2]
输出：[1]
解释：交换节点 2 和 3 来翻转节点 1 ，先序遍历可以匹配预期行程。

示例 3：

输入：root = [1,2,3], voyage = [1,2,3]
输出：[]
解释：先序遍历已经匹配预期行程，所以不需要翻转节点。

提示：

树中的节点数目为 n
n == voyage.length
1 <= n <= 100
1 <= Node.val, voyage[i] <= n
树中的所有值 互不相同
voyage 中的所有值 互不相同

方法一：DFS · Go 实现

思考

若干次左右翻转后，先序是否能等于 $voyage$ 。值互不相同，当前结点必须对上 $voyage [i]$ 。若左孩子存在且不等于下一个期望值，则必须翻转并先走右子树。一次 DFS 同时推进下标，失败则返回 $[- 1]$ 。

我们可以通过深度优先搜索的方式遍历整棵树，用一个下标 $i$ 记录当前遍历到的节点在数组 $voyage$ 中的下标，如果当前遍历到的节点的值不等于 $voyage [i]$ ，那么说明翻转后无法匹配，我们标记 $ok$ 为 false，并直接返回。否则，我们将 $i$ 的值加 $1$ ，然后判断当前节点是否有左子节点，如果没有，或者左子节点的值等于 $voyage [i]$ ，那么我们递归遍历当前的左右子节点；否则，我们需要翻转当前节点，然后再递归遍历当前的右子节点和左子节点。

搜索结束后，如果 $ok$ 为 true，那么说明翻转后可以匹配，我们返回答案数组 $ans$ ，否则返回 $[- 1]$ 。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 是树中的节点数目。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func flipMatchVoyage(root *TreeNode, voyage []int) []int {
	i := 0
	ok := true
	ans := []int{}
	var dfs func(*TreeNode)
	dfs = func(root *TreeNode) {
		if root == nil || !ok {
			return
		}
		if root.Val != voyage[i] {
			ok = false
			return
		}
		i++
		if root.Left == nil || root.Left.Val == voyage[i] {
			dfs(root.Left)
			dfs(root.Right)
		} else {
			ans = append(ans, root.Val)
			dfs(root.Right)
			dfs(root.Left)
		}
	}
	dfs(root)
	if !ok {
		return []int{-1}
	}
	return ans
}

力扣原题 · Doocs 题解来源

979. 在二叉树中分配硬币

中等1 种解法

标签：树、深度优先搜索、二叉树、树形 DP

题目、示例与约束

给你一个有 n 个结点的二叉树的根结点 root ，其中树中每个结点 node 都对应有 node.val 枚硬币。整棵树上一共有 n 枚硬币。

在一次移动中，我们可以选择两个相邻的结点，然后将一枚硬币从其中一个结点移动到另一个结点。移动可以是从父结点到子结点，或者从子结点移动到父结点。

返回使每个结点上只有一枚硬币所需的最少移动次数。

示例 1：

输入：root = [3,0,0]
输出：2
解释：一枚硬币从根结点移动到左子结点，一枚硬币从根结点移动到右子结点。

示例 2：

输入：root = [0,3,0]
输出：3
解释：将两枚硬币从根结点的左子结点移动到根结点（两次移动）。然后，将一枚硬币从根结点移动到右子结点。

提示：

树中节点的数目为 n
1 <= n <= 100
0 <= Node.val <= n
所有 Node.val 的值之和是 n

方法一：DFS · Go 实现

思考

边上流过一枚金币计一次移动，使每结点恰有一枚。全局规划路径复杂，但子树的盈亏必须经过根边：超载量 $= 子树金币 - 结点数$ ，其绝对值即经过该边的次数。DFS 累加左右超载的绝对值并向上返回。

我们定义一个函数 $dfs(node)$ ，表示以 $node$ 为根节点的子树中，金币的超载量，即金币的数量减去节点数。如果 $dfs(node)$ 为正数，表示该子树中金币的数量多于节点数，需要将多余的金币移出该子树；如果 $dfs(node)$ 为负数，表示该子树中金币的数量少于节点数，需要将不足的金币移入该子树。

在函数 $dfs(node)$ 中，我们首先遍历左右子树，获得左右子树的金币超载量 $left$ 和 $right$ 。那么当前移动的次数需要加上 $| left | + | right |$ ，即将左右子树中的金币移动到当前节点。然后，我们返回整个子树的金币超载量，即 $left + right + node.val - 1$ 。

最后返回移动的次数即可。

时间复杂度 $O (n)$ ，空间复杂度 $O (h)$ 。其中 $n$ 和 $h$ 分别是二叉树的节点数和高度。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func distributeCoins(root *TreeNode) (ans int) {
	var dfs func(*TreeNode) int
	dfs = func(root *TreeNode) int {
		if root == nil {
			return 0
		}
		left, right := dfs(root.Left), dfs(root.Right)
		ans += abs(left) + abs(right)
		return left + right + root.Val - 1
	}
	dfs(root)
	return
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

力扣原题 · Doocs 题解来源

987. 二叉树的垂序遍历

困难1 种解法

标签：树、深度优先搜索、广度优先搜索、哈希表、二叉树、排序

题目、示例与约束

给你二叉树的根结点 root ，请你设计算法计算二叉树的 垂序遍历 序列。

对位于 (row, col) 的每个结点而言，其左右子结点分别位于 (row + 1, col - 1) 和 (row + 1, col + 1) 。树的根结点位于 (0, 0) 。

二叉树的 垂序遍历 从最左边的列开始直到最右边的列结束，按列索引每一列上的所有结点，形成一个按出现位置从上到下排序的有序列表。如果同行同列上有多个结点，则按结点的值从小到大进行排序。

返回二叉树的 垂序遍历 序列。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[9],[3,15],[20],[7]]
解释：
列 -1 ：只有结点 9 在此列中。
列  0 ：只有结点 3 和 15 在此列中，按从上到下顺序。
列  1 ：只有结点 20 在此列中。
列  2 ：只有结点 7 在此列中。

示例 2：

输入：root = [1,2,3,4,5,6,7]
输出：[[4],[2],[1,5,6],[3],[7]]
解释：
列 -2 ：只有结点 4 在此列中。
列 -1 ：只有结点 2 在此列中。
列  0 ：结点 1 、5 和 6 都在此列中。
          1 在上面，所以它出现在前面。
          5 和 6 位置都是 (2, 0) ，所以按值从小到大排序，5 在 6 的前面。
列  1 ：只有结点 3 在此列中。
列  2 ：只有结点 7 在此列中。

示例 3：

输入：root = [1,2,3,4,6,5,7]
输出：[[4],[2],[1,5,6],[3],[7]]
解释：
这个示例实际上与示例 2 完全相同，只是结点 5 和 6 在树中的位置发生了交换。
因为 5 和 6 的位置仍然相同，所以答案保持不变，仍然按值从小到大排序。

提示：

树中结点数目总数在范围 [1, 1000] 内
0 <= Node.val <= 1000

方法一：DFS + 排序 · Go 实现

思考

按列从左到右输出结点，同列先按行、再按值排序。DFS 记下 $(c o l, r o w, v a l)$ ，一次排序即可按题目规定的三关键字分组输出。

我们设计一个函数 $d f s (r o o t, i, j)$ ，其中 $i$ 和 $j$ 表示当前节点的行和列。我们可以通过深度优先搜索的方式，将节点的行和列信息记录下来，存储在一个数组或列表 $n o d e s$ 中，然后对 $n o d e s$ 按照列、行、值的顺序进行排序。

接着，我们遍历 $n o d e s$ ，将相同列的节点值放到同一个列表中，最后返回这些列表。

时间复杂度 $O (n \times \log n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 是二叉树的节点数。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func verticalTraversal(root *TreeNode) (ans [][]int) {
	nodes := [][3]int{}
	var dfs func(*TreeNode, int, int)
	dfs = func(root *TreeNode, i, j int) {
		if root == nil {
			return
		}
		nodes = append(nodes, [3]int{j, i, root.Val})
		dfs(root.Left, i+1, j-1)
		dfs(root.Right, i+1, j+1)
	}
	dfs(root, 0, 0)
	sort.Slice(nodes, func(i, j int) bool {
		a, b := nodes[i], nodes[j]
		return a[0] < b[0] || a[0] == b[0] && (a[1] < b[1] || a[1] == b[1] && a[2] < b[2])
	})
	prev := -2000
	for _, node := range nodes {
		j, val := node[0], node[2]
		if j != prev {
			ans = append(ans, nil)
			prev = j
		}
		ans[len(ans)-1] = append(ans[len(ans)-1], val)
	}
	return
}

力扣原题 · Doocs 题解来源

988. 从叶结点开始的最小字符串

中等1 种解法

标签：树、深度优先搜索、字符串、回溯、二叉树

题目、示例与约束

给定一颗根结点为 root 的二叉树，树中的每一个结点都有一个 [0, 25] 范围内的值，分别代表字母 'a' 到 'z'。

返回 按字典序最小 的字符串，该字符串从这棵树的一个叶结点开始，到根结点结束。

注：字符串中任何较短的前缀在 字典序上 都是较小的：

例如，在字典序上 "ab" 比 "aba" 要小。叶结点是指没有子结点的结点。

节点的叶节点是没有子节点的节点。

示例 1：

输入：root = [0,1,2,3,4,3,4]
输出："dba"

示例 2：

输入：root = [25,1,3,1,3,0,2]
输出："adz"

示例 3：

输入：root = [2,2,1,null,1,0,null,0]
输出："abc"

提示：

给定树的结点数在 [1, 8500] 范围内
0 <= Node.val <= 25

方法一 · Go 实现

思考

从叶到根的路径看成字母串，求字典序最小者。结点至多 $8500$ ，可枚举所有根到叶路径。DFS 沿途把字母压栈，到达叶子时反转与当前答案比较，回溯弹栈。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func smallestFromLeaf(root *TreeNode) string {
	ans := ""
	var dfs func(root *TreeNode, path string)
	dfs = func(root *TreeNode, path string) {
		if root == nil {
			return
		}
		path = string('a'+root.Val) + path
		if root.Left == nil && root.Right == nil {
			if ans == "" || path < ans {
				ans = path
			}
			return
		}
		dfs(root.Left, path)
		dfs(root.Right, path)
	}

	dfs(root, "")
	return ans
}

力扣原题 · Doocs 题解来源

993. 二叉树的堂兄弟节点

简单2 种解法

标签：树、深度优先搜索、广度优先搜索、二叉树

题目、示例与约束

在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k+1 处。

如果二叉树的两个节点深度相同，但 父节点不同 ，则它们是一对堂兄弟节点。

我们给出了具有唯一值的二叉树的根节点 root ，以及树中两个不同节点的值 x 和 y 。

只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 true 。否则，返回 false。

示例 1：

输入：root = [1,2,3,4], x = 4, y = 3
输出：false

示例 2：

输入：root = [1,2,3,null,4,null,5], x = 5, y = 4
输出：true

示例 3：

输入：root = [1,2,3,null,4], x = 2, y = 3
输出：false

提示：

二叉树的节点数介于 2 到 100 之间。
每个节点的值都是唯一的、范围为 1 到 100 的整数。

方法一：BFS · Go 实现

思考

堂兄弟深度相同且父结点不同。层序时一并带上父结点，遇到 $x, y$ 记下父与层，整层扫完后比较即可。

我们定义一个队列 $q$ ，队列中存储的是节点和其父节点。初始时，将根节点和空节点放入队列中。

每次从队列中取出一个节点，如果该节点的值为 $x$ 或 $y$ ，则记录该节点的父节点和深度。如果该节点的左右子节点不为空，则将左右子节点和该节点放入队列中。

当队列中所有节点都处理完毕后，如果 $x$ 和 $y$ 的深度相同且父节点不同，则返回 $t r u e$ ，否则返回 $f a l s e$ 。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 是二叉树的节点数。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isCousins(root *TreeNode, x int, y int) bool {
	type pair struct{ node, parent *TreeNode }
	var d1, d2 int
	var p1, p2 *TreeNode
	q := []pair{{root, nil}}
	for depth := 0; len(q) > 0; depth++ {
		for n := len(q); n > 0; n-- {
			node, parent := q[0].node, q[0].parent
			q = q[1:]
			if node.Val == x {
				d1, p1 = depth, parent
			} else if node.Val == y {
				d2, p2 = depth, parent
			}
			if node.Left != nil {
				q = append(q, pair{node.Left, node})
			}
			if node.Right != nil {
				q = append(q, pair{node.Right, node})
			}
		}
	}
	return d1 == d2 && p1 != p2
}

方法二：DFS · Go 实现

思考

BFS 按层推进。DFS 同样可以：递归时传入父结点与深度，找到 $x, y$ 后比较父与深度是否满足堂兄弟定义。

我们设计一个函数 $d f s (r o o t, p a r e n t, d e p t h)$ ，表示从根节点 $r o o t$ 出发，其父节点为 $p a r e n t$ ，深度为 $d e p t h$ ，进行深度优先搜索。

在函数中，我们首先判断当前节点是否为空，如果为空，则直接返回。如果当前节点的值为 $x$ 或 $y$ ，则记录该节点的父节点和深度。然后对当前节点的左右子节点分别调用函数 $d f s$ ，其中父节点为当前节点，深度为当前深度加 $1$ 。即 $d f s (r o o t . l e f t, r o o t, d e p t h + 1)$ 和 $d f s (r o o t . r i g h t, r o o t, d e p t h + 1)$ 。

当整棵二叉树遍历完毕后，如果 $x$ 和 $y$ 的深度相同且父节点不同，则返回 $t r u e$ ，否则返回 $f a l s e$ 。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 是二叉树的节点数。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isCousins(root *TreeNode, x int, y int) bool {
	var d1, d2 int
	var p1, p2 *TreeNode
	var dfs func(root, parent *TreeNode, depth int)
	dfs = func(root, parent *TreeNode, depth int) {
		if root == nil {
			return
		}
		if root.Val == x {
			d1, p1 = depth, parent
		} else if root.Val == y {
			d2, p2 = depth, parent
		}
		dfs(root.Left, root, depth+1)
		dfs(root.Right, root, depth+1)
	}
	dfs(root, nil, 0)
	return d1 == d2 && p1 != p2
}

力扣原题 · Doocs 题解来源

998. 最大二叉树 II

中等2 种解法

标签：树、二叉树

题目、示例与约束

最大树 定义：一棵树，并满足：其中每个节点的值都大于其子树中的任何其他值。

给你最大树的根节点 root 和一个整数 val 。

就像之前的问题那样，给定的树是利用 Construct(a) 例程从列表 a（root = Construct(a)）递归地构建的：

如果 a 为空，返回 null 。
否则，令 a[i] 作为 a 的最大元素。创建一个值为 a[i] 的根节点 root 。
root 的左子树将被构建为 Construct([a[0], a[1], ..., a[i - 1]]) 。
root 的右子树将被构建为 Construct([a[i + 1], a[i + 2], ..., a[a.length - 1]]) 。
返回 root 。

请注意，题目没有直接给出 a ，只是给出一个根节点 root = Construct(a) 。

假设 b 是 a 的副本，并在末尾附加值 val。题目数据保证 b 中的值互不相同。

返回 Construct(b) 。

示例 1：

输入：root = [4,1,3,null,null,2], val = 5
输出：[5,4,null,1,3,null,null,2]
解释：a = [1,4,2,3], b = [1,4,2,3,5]

示例 2：

输入：root = [5,2,4,null,1], val = 3
输出：[5,2,4,null,1,null,3]
解释：a = [2,1,5,4], b = [2,1,5,4,3]

示例 3：

输入：root = [5,2,3,null,1], val = 4
输出：[5,2,4,null,1,3]
解释：a = [2,1,5,3], b = [2,1,5,3,4]

提示：

树中节点数目在范围 [1, 100] 内
1 <= Node.val <= 100
树中的所有值 互不相同
1 <= val <= 100

方法一：递归 · Go 实现

思考

在最大二叉树对应的数组末尾追加 $v a l$ 再重建。 $v a l$ 若大于根则成为新根，原树作左子树；否则 $v a l$ 只可能落在右脊上。沿右子树递归插入即可。

如果 $v a l$ 是最大数，那么将 $v a l$ 作为新的根节点， $r o o t$ 作为新的根节点的左子树。

如果 $v a l$ 不是最大数，由于 $v a l$ 是在最后追加的数，那么一定是在 $r o o t$ 的右边，所以将 $v a l$ 作为新节点插入 $r o o t$ 的右子树即可。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 是树的节点数。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func insertIntoMaxTree(root *TreeNode, val int) *TreeNode {
	if root == nil || root.Val < val {
		return &TreeNode{val, root, nil}
	}
	root.Right = insertIntoMaxTree(root.Right, val)
	return root
}

方法二：迭代 · Go 实现

思考

递归深度最坏为树高。改为沿右链迭代，找到第一个右孩子小于 $v a l$ 的位置，把旧右子树接到新结点左侧，避免递归栈。

搜索右子树，找到 $c u r r . v a l > v a l > c u r r . r i g h t . v a l$ 的节点，然后创建新的节点 $n o d e$ ，把 $n o d e . l e f t$ 指向 $c u r r . r i g h t$ ，然后 $c u r r . r i g h t$ 指向 $n o d e$ 。

最后返回 $r o o t$ 。

时间复杂度 $O (n)$ ，其中 $n$ 是树的节点数。空间复杂度 $O (1)$ 。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func insertIntoMaxTree(root *TreeNode, val int) *TreeNode {
	if root.Val < val {
		return &TreeNode{val, root, nil}
	}
	node := &TreeNode{Val: val}
	curr := root
	for curr.Right != nil && curr.Right.Val > val {
		curr = curr.Right
	}
	node.Left = curr.Right
	curr.Right = node
	return root
}

力扣原题 · Doocs 题解来源

1008. 前序遍历构造二叉搜索树

中等1 种解法

标签：栈、树、二叉搜索树、数组、二叉树、单调栈

题目、示例与约束

给定一个整数数组，它表示BST(即 二叉搜索树 )的先序遍历 ，构造树并返回其根。

保证对于给定的测试用例，总是有可能找到具有给定需求的二叉搜索树。

二叉搜索树 是一棵二叉树，其中每个节点， Node.left 的任何后代的值 严格小于 Node.val , Node.right 的任何后代的值 严格大于 Node.val。

二叉树的 前序遍历 首先显示节点的值，然后遍历Node.left，最后遍历Node.right。

示例 1：

输入：preorder = [8,5,1,7,10,12]
输出：[8,5,10,1,7,null,12]

示例 2:

输入: preorder = [1,3]
输出: [1,null,3]

提示：

1 <= preorder.length <= 100
1 <= preorder[i] <= 10^8
preorder 中的值 互不相同

方法一：DFS + 二分查找 · Go 实现

思考

先序首元素为根，其后线性扫描找到第一个更大的值即可划分左右子树， $n \leq 100$ 时 $O (n^{2})$ 可过，但每次划分都重复走过多段。

先序在 BST 上的片段仍保持「左子树键均小于根、右子树键均大于根」，且左段之后的元素单调地大于根，因此第一个大于根的下标可以用二分找到。

递归 $dfs (i, j)$ 以 $preorder [i]$ 为根，二分得到右子树起点后再构造两侧，总时间 $O (n \log n)$ 。

我们设计一个函数 $dfs (i, j)$ ，表示构造出从 $preorder [i]$ 到 $preorder [j]$ 这些节点构成的二叉搜索树。那么答案就是 $dfs (0, n - 1)$ 。

在 $dfs (i, j)$ 中，我们首先构造根节点，即 $preorder [i]$ 。然后使用二分查找的方法找到第一个大于 $preorder [i]$ 的节点的下标 $mid$ ，将 $dfs (i + 1, mid - 1)$ 作为根节点的左子树，将 $dfs (mid, j)$ 作为根节点的右子树。

最后返回根节点即可。

时间复杂度 $O (n \times \log n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 为数组 $preorder$ 的长度。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func bstFromPreorder(preorder []int) *TreeNode {
	var dfs func(i, j int) *TreeNode
	dfs = func(i, j int) *TreeNode {
		if i > j {
			return nil
		}
		root := &TreeNode{Val: preorder[i]}
		l, r := i+1, j+1
		for l < r {
			mid := (l + r) >> 1
			if preorder[mid] > preorder[i] {
				r = mid
			} else {
				l = mid + 1
			}
		}
		root.Left = dfs(i+1, l-1)
		root.Right = dfs(l, j)
		return root
	}
	return dfs(0, len(preorder)-1)
}

力扣原题 · Doocs 题解来源

1022. 从根到叶的二进制数之和

简单1 种解法

标签：树、深度优先搜索、二叉树

题目、示例与约束

给出一棵二叉树，其上每个结点的值都是 0 或 1 。每一条从根到叶的路径都代表一个从最高有效位开始的二进制数。

例如，如果路径为 0 -> 1 -> 1 -> 0 -> 1，那么它表示二进制数 01101，也就是 13 。

对树上的每一片叶子，我们都要找出从根到该叶子的路径所表示的数字。

返回这些数字之和。题目数据保证答案是一个 32 位 整数。

示例 1：

输入：root = [1,0,1,0,1,0,1]
输出：22
解释：(100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22

示例 2：

输入：root = [0]
输出：0

提示：

树中的节点数在 [1, 1000] 范围内
Node.val 仅为 0 或 1

方法一：递归 · Go 实现

思考

先列出根到叶的每条路径再把二进制转成整数相加， $n \leq 1000$ 可行，但路径要额外存储。从根走下时，路径值满足 $t \leftarrow 2 t + val$ ，到达叶子即可结算。

空节点贡献 $0$ ；左右皆空视为叶子，返回当前 $t$ ；否则把同一 $t$ 交给左右子树相加。

深度优先带着路径值下行，每个节点访问一次。

我们设计一个递归函数 $dfs (r o o t, t)$ ，它接收两个参数：当前节点 $r o o t$ 和当前节点的父节点对应的二进制数 $t$ 。函数的返回值是从当前节点到叶子节点的路径所表示的二进制数之和。答案即为 $dfs (r o o t, 0)$ 。

递归函数的逻辑如下：

如果当前节点 $r o o t$ 为空，则返回 $0$ ，否则计算当前节点对应的二进制数 $t$ ，即 $t = t ≪ 1 | r o o t . v a l$ 。
如果当前节点是叶子节点，则返回 $t$ ，否则返回 $dfs (r o o t . l e f t, t)$ 和 $dfs (r o o t . r i g h t, t)$ 的和。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 是二叉树的节点数。对每个节点访问一次；递归栈需要 $O (n)$ 的空间。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sumRootToLeaf(root *TreeNode) int {
	var dfs func(*TreeNode, int) int
	dfs = func(root *TreeNode, x int) int {
		if root == nil {
			return 0
		}
		x = x<<1 | root.Val
		if root.Left == root.Right {
			return x
		}
		return dfs(root.Left, x) + dfs(root.Right, x)
	}
	return dfs(root, 0)
}

力扣原题 · Doocs 题解来源

1026. 节点与其祖先之间的最大差值

中等1 种解法

标签：树、深度优先搜索、二叉树

题目、示例与约束

给定二叉树的根节点 root，找出存在于不同节点 A 和 B 之间的最大值 V，其中 V = |A.val - B.val|，且 A 是 B 的祖先。

（如果 A 的任何子节点之一为 B，或者 A 的任何子节点是 B 的祖先，那么我们认为 A 是 B 的祖先）

示例 1：

输入：root = [8,3,10,1,6,null,14,null,null,4,7,13]
输出：7
解释： 
我们有大量的节点与其祖先的差值，其中一些如下：
|8 - 3| = 5
|3 - 7| = 4
|8 - 1| = 7
|10 - 13| = 3
在所有可能的差值中，最大值 7 由 |8 - 1| = 7 得出。

示例 2：

输入：root = [1,null,2,null,0,3]
输出：3

提示：

树中的节点数在 2 到 5000 之间。
0 <= Node.val <= 10⁵

方法一：DFS · Go 实现

思考

对每个节点向上收集全部祖先再求最大差， $n \leq 5000$ 时路径重复、时间偏大。路径上真正用到的只有祖先的最小值与最大值。

下行时把当前路径的 $mi, mx$ 传给子节点，在每个节点用 $| val - mi |$ 与 $| val - mx |$ 更新全局答案，再把本节点纳入区间后继续。

一次 DFS 遍历整棵树即可。

对于每个节点，求其与祖先节点的最大差值，我们只需要求出该节点与祖先节点最大值和最小值的差值。取所有节点与祖先节点差值的最大值即可。

因此，我们设计一个函数 $d f s (r o o t, m i, m x)$ ，表示当前搜索到的节点为 $r o o t$ ，其祖先节点的最大值为 $m x$ ，最小值为 $m i$ ，函数内更新最大差值 $a n s$ 。

函数 $d f s (r o o t, m i, m x)$ 的逻辑如下：

若 $r o o t$ 为空，直接返回。
否则，我们更新 $a n s = m a x (a n s, | m i - r o o t . v a l |, | m x - r o o t . v a l |)$ 。
然后更新 $m i = m i n (m i, r o o t . v a l)$ , $m x = m a x (m x, r o o t . v a l)$ ，并且递归搜索左右子树。

在主函数中，我们调用 $d f s (r o o t, r o o t . v a l, r o o t . v a l)$ ，最后返回 $a n s$ 即可。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 为二叉树节点个数。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func maxAncestorDiff(root *TreeNode) (ans int) {
	var dfs func(*TreeNode, int, int)
	dfs = func(root *TreeNode, mi, mx int) {
		if root == nil {
			return
		}
		ans = max(ans, max(abs(mi-root.Val), abs(mx-root.Val)))
		mi = min(mi, root.Val)
		mx = max(mx, root.Val)
		dfs(root.Left, mi, mx)
		dfs(root.Right, mi, mx)
	}
	dfs(root, root.Val, root.Val)
	return
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

力扣原题 · Doocs 题解来源

1028. 从先序遍历还原二叉树

困难1 种解法

标签：树、深度优先搜索、字符串、二叉树

题目、示例与约束

我们从二叉树的根节点 root 开始进行深度优先搜索。

在遍历中的每个节点处，我们输出 D 条短划线（其中 D 是该节点的深度），然后输出该节点的值。（如果节点的深度为 D，则其直接子节点的深度为 D + 1。根节点的深度为 0）。

如果节点只有一个子节点，那么保证该子节点为左子节点。

给出遍历输出 S，还原树并返回其根节点 root。

示例 1：

输入："1-2--3--4-5--6--7"
输出：[1,2,5,3,4,6,7]

示例 2：

输入："1-2--3---4-5--6---7"
输出：[1,2,5,3,null,6,null,4,null,7]

示例 3：

输入："1-401--349---90--88"
输出：[1,401,null,349,88,90]

提示：

原始树中的节点数介于 1 和 1000 之间。
每个节点的值介于 1 和 10 ^ 9 之间。

方法一：Go 实现（halfrost） · Go 实现

halfrost · 源码 · MIT 许可

本次根据原始 Go 源码整理的中文说明，非 halfrost 书籍原文。

通过短横线数量识别节点深度，通过连续数字解析节点值；递归函数结合当前位置和期望层级，将子节点依次接到左、右位置。主函数使用临时根节点，并返回其右子树作为真正结果。原有 TreeNode 类型别名和仓库导入路径均保留。

本站仅将仓库的 structures.TreeNode 改为力扣提供的 TreeNode，并移除该仓库导入；算法未改。

import (
	"strconv"
)

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func recoverFromPreorder(S string) *TreeNode {
	if len(S) == 0 {
		return &TreeNode{}
	}
	root, index, level := &TreeNode{}, 0, 0
	cur := root
	dfsBuildPreorderTree(S, &index, &level, cur)
	return root.Right
}

func dfsBuildPreorderTree(S string, index, level *int, cur *TreeNode) (newIndex *int) {
	if *index == len(S) {
		return index
	}
	if *index == 0 && *level == 0 {
		i := 0
		for i = *index; i < len(S); i++ {
			if !isDigital(S[i]) {
				break
			}
		}
		num, _ := strconv.Atoi(S[*index:i])
		tmp := &TreeNode{Val: num, Left: nil, Right: nil}
		cur.Right = tmp
		nLevel := *level + 1
		index = dfsBuildPreorderTree(S, &i, &nLevel, tmp)
		index = dfsBuildPreorderTree(S, index, &nLevel, tmp)
	}
	i := 0
	for i = *index; i < len(S); i++ {
		if isDigital(S[i]) {
			break
		}
	}
	if *level == i-*index {
		j := 0
		for j = i; j < len(S); j++ {
			if !isDigital(S[j]) {
				break
			}
		}
		num, _ := strconv.Atoi(S[i:j])
		tmp := &TreeNode{Val: num, Left: nil, Right: nil}
		if cur.Left == nil {
			cur.Left = tmp
			nLevel := *level + 1
			index = dfsBuildPreorderTree(S, &j, &nLevel, tmp)
			index = dfsBuildPreorderTree(S, index, level, cur)
		} else if cur.Right == nil {
			cur.Right = tmp
			nLevel := *level + 1
			index = dfsBuildPreorderTree(S, &j, &nLevel, tmp)
			index = dfsBuildPreorderTree(S, index, level, cur)
		}
	}
	return index
}

func isDigital(v byte) bool {
	if v >= '0' && v <= '9' {
		return true
	}
	return false
}

力扣原题 · Doocs 题解来源

1038. 从二叉搜索树到更大和树

中等2 种解法

标签：树、深度优先搜索、二叉搜索树、二叉树

题目、示例与约束

给定一个二叉搜索树 root (BST)，请将它的每个节点的值替换成树中大于或者等于该节点值的所有节点值之和。

提醒一下， 二叉搜索树 满足下列约束条件：

节点的左子树仅包含键小于节点键的节点。
节点的右子树仅包含键大于节点键的节点。
左右子树也必须是二叉搜索树。

示例 1：

输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

示例 2：

输入：root = [0,null,1]
输出：[1,null,1]

提示：

树中的节点数在 [1, 100] 范围内。
0 <= Node.val <= 100
树中的所有值均 不重复 。

注意：该题目与 538: https://leetcode.cn/problems/convert-bst-to-greater-tree/ 相同

方法一：递归 · Go 实现

思考

每个节点应换成不小于它的所有键之和。BST 的反序中序（右、根、左）恰按键从大到小访问，沿途累加即可就地改写。 $n \leq 100$ ，递归深度可接受。

先递归右子树，把当前值加入总和 $s$ 并写回，再递归左子树。

一遍遍历完成转换。

按照“右根左”的顺序，递归遍历二叉搜索树，累加遍历到的所有节点值到 $s$ 中，然后每次赋值给对应的 node 节点。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 是二叉搜索树的节点数。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func bstToGst(root *TreeNode) *TreeNode {
	s := 0
	var dfs func(*TreeNode)
	dfs = func(root *TreeNode) {
		if root == nil {
			return
		}
		dfs(root.Right)
		s += root.Val
		root.Val = s
		dfs(root.Left)
	}
	dfs(root)
	return root
}

方法二：Morris 遍历 · Go 实现

思考

递归栈随树高增长，进阶希望额外空间 $O (1)$ 。Morris 遍历用空的右子树最左指针暂存后继，可在不使用栈的情况下完成同一「右根左」顺序。

当前节点无右子则结算并走向左；有右子则找到后继：尚未穿线则先穿到自己再向右，已穿线则结算、拆线并走向左。累加规则与方法一相同。

Morris 遍历无需使用栈，时间复杂度 $O (n)$ ，空间复杂度为 $O (1)$ 。核心思想是：

定义 s 表示二叉搜索树节点值累加和。遍历二叉树节点：

若当前节点 root 的右子树为空，将当前节点值添加至 s 中，更新当前节点值为 s，并将当前节点更新为 root.left。
若当前节点 root 的右子树不为空，找到右子树的最左节点 next（也即是 root 节点在中序遍历下的后继节点）：
- 若后继节点 next 的左子树为空，将后继节点的左子树指向当前节点 root，并将当前节点更新为 root.right。
- 若后继节点 next 的左子树不为空，将当前节点值添加 s 中，更新当前节点值为 s，然后将后继节点左子树指向空（即解除 next 与 root 的指向关系），并将当前节点更新为 root.left。
循环以上步骤，直至二叉树节点为空，遍历结束。
最后返回二叉搜索树根节点即可。

Morris 反序中序遍历跟 Morris 中序遍历思路一致，只是将中序遍历的“左根右”变为“右根左”。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func bstToGst(root *TreeNode) *TreeNode {
	s := 0
	node := root
	for root != nil {
		if root.Right == nil {
			s += root.Val
			root.Val = s
			root = root.Left
		} else {
			next := root.Right
			for next.Left != nil && next.Left != root {
				next = next.Left
			}
			if next.Left == nil {
				next.Left = root
				root = root.Right
			} else {
				s += root.Val
				root.Val = s
				next.Left = nil
				root = root.Left
			}
		}
	}
	return node
}

力扣原题 · Doocs 题解来源

1080. 根到叶路径上的不足节点

中等1 种解法

标签：树、深度优先搜索、二叉树

题目、示例与约束

给你二叉树的根节点 root 和一个整数 limit ，请你同时删除树中所有 不足节点 ，并返回最终二叉树的根节点。

假如通过节点 node 的每种可能的 “根-叶” 路径上值的总和全都小于给定的 limit，则该节点被称之为 不足节点 ，需要被删除。

叶子节点，就是没有子节点的节点。

示例 1：

输入：root = [1,2,3,4,-99,-99,7,8,9,-99,-99,12,13,-99,14], limit = 1
输出：[1,2,3,4,null,null,7,8,9,null,14]

示例 2：

输入：root = [5,4,8,11,null,17,4,7,1,null,null,5,3], limit = 22
输出：[5,4,8,11,null,17,4,7,null,null,null,5]

示例 3：

输入：root = [1,2,-3,-5,null,4,null], limit = -1
输出：[1,null,-3,4]

提示：

树中节点数目在范围 [1, 5000] 内
-10⁵ <= Node.val <= 10⁵
-10⁹ <= limit <= 10⁹

方法一：递归 · Go 实现

思考

要删掉所有根到叶路径和小于 $limit$ 的节点。从叶往上：一条路径的合法性在叶子才能判定，父节点仅当左右都删光时才失去存在意义。 $n \leq 5000$ ，一次后序即可。

下行时把 $limit$ 减去当前值。叶子在剩余 $limit > 0$ 时删除。内部节点先处理左右孩子，若两边都空则自身也删。

返回新的子树根，可能为空。

我们递归遍历整棵树，对于当前遍历到的节点 $r o o t$ ：

如果 $r o o t$ 为空，那么返回空；否则，我们将 $l i m i t$ 减去当前节点的值，即 $l i m i t = l i m i t - r o o t . v a l$ ，然后继续执行下述步骤。

如果 $r o o t$ 为叶子节点（即 $r o o t$ 的左右子节点都为空），说明我们已经走完了一条从根节点到叶子节点的路径。如果此时 $l i m i t > 0$ ，说明该路径上所有节点的值的和小于 $l i m i t$ ，我们返回空节点，表示删除；否则，说明该路径上所有节点的值的和大于等于 $l i m i t$ ，我们返回 $r o o t$ 。

如果 $r o o t$ 不是叶子节点，那么我们递归调用函数 $s u f f i c i e n t S u b s e t$ ，对 $r o o t$ 的左右子节点分别进行处理，并将返回值分别赋值给 $r o o t$ 的左右子节点。

如果 $r o o t$ 的左右子节点在经过递归调用后变成了空节点，那么说明 $r o o t$ 的左右子树中所有从根节点到叶子节点的路径上所有节点的值的和都小于 $l i m i t$ ，因此我们返回空节点，表示删除 $r o o t$ ；否则，说明 $r o o t$ 的左右子树中存在从根节点到叶子节点上所有节点值的和大于等于 $l i m i t$ 的路径，因此我们返回 $r o o t$ 。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 是二叉树的节点个数。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sufficientSubset(root *TreeNode, limit int) *TreeNode {
	if root == nil {
		return nil
	}

	limit -= root.Val
	if root.Left == nil && root.Right == nil {
		if limit > 0 {
			return nil
		}
		return root
	}

	root.Left = sufficientSubset(root.Left, limit)
	root.Right = sufficientSubset(root.Right, limit)

	if root.Left == nil && root.Right == nil {
		return nil
	}
	return root
}

力扣原题 · Doocs 题解来源

1104. 二叉树寻路

中等1 种解法

标签：树、数学、二叉树

题目、示例与约束

在一棵无限的二叉树上，每个节点都有两个子节点，树中的节点逐行依次按 “之” 字形进行标记。

如下图所示，在奇数行（即，第一行、第三行、第五行……）中，按从左到右的顺序进行标记；

而偶数行（即，第二行、第四行、第六行……）中，按从右到左的顺序进行标记。

给你树上某一个节点的标号 label，请你返回从根节点到该标号为 label 节点的路径，该路径是由途经的节点标号所组成的。

示例 1：

输入：label = 14
输出：[1,3,4,14]

示例 2：

输入：label = 26
输出：[1,2,6,10,26]

提示：

1 <= label <= 10^6

方法一：数学 · Go 实现

思考

普通完全二叉树中父结点为 $⌊ label / 2 ⌋$ ，但本题奇数行与偶数行标记方向相反，该公式不再成立。第 $i$ 层编号区间为 $[2^{i - 1}, 2^{i} - 1]$ ，反向层上结点关于区间中心对称，互补编号为 $2^{i - 1} + 2^{i} - 1 - label$ ，真实父结点即该互补编号除以 $2$ 。

先求出 $label$ 所在层数，再自底向上反复取互补并右移，把路径写入对应下标，自然得到从根到该结点的序列。

对于一棵完全二叉树，第 $i$ 行的节点个数为 $2^{i - 1}$ ，第 $i$ 行的节点编号范围为 $[2^{i - 1}, 2^{i} - 1]$ 。而题目中对于奇数行，按从左到右的顺序进行标记，对于偶数行，按从右到左的顺序进行标记。所以对于第 $i$ 行的节点 $l a b e l$ ，它的互补节点编号为 $2^{i - 1} + 2^{i} - 1 - l a b e l$ 。所以节点 $l a b e l$ 的实际父节点编号为 $(2^{i - 1} + 2^{i} - 1 - l a b e l) / 2$ 。我们可以通过不断地求互补节点编号和父节点编号，直到到达根节点，即可得到从根节点到节点 $l a b e l$ 的路径。

最后，我们需要将路径反转，因为题目要求路径是从根节点到节点 $l a b e l$ 的路径。

时间复杂度 $O (\log n)$ ，其中 $n$ 为节点 $l a b e l$ 的编号。忽略答案的空间消耗，空间复杂度 $O (1)$ 。

func pathInZigZagTree(label int) (ans []int) {
	x, i := 1, 1
	for x<<1 <= label {
		x <<= 1
		i++
	}
	for ; i > 0; i-- {
		ans = append(ans, label)
		label = ((1 << (i - 1)) + (1 << i) - 1 - label) >> 1
	}
	for i, j := 0, len(ans)-1; i < j; i, j = i+1, j-1 {
		ans[i], ans[j] = ans[j], ans[i]
	}
	return
}

力扣原题 · Doocs 题解来源

1110. 删点成林

中等1 种解法

标签：树、深度优先搜索、数组、哈希表、二叉树

题目、示例与约束

给出二叉树的根节点 root，树上每个节点都有一个不同的值。

如果节点值在 to_delete 中出现，我们就把该节点从树上删去，最后得到一个森林（一些不相交的树构成的集合）。

返回森林中的每棵树。你可以按任意顺序组织答案。

示例 1：

输入：root = [1,2,3,4,5,6,7], to_delete = [3,5]
输出：[[1,2,null,4],[6],[7]]

示例 2：

输入：root = [1,2,4,null,3], to_delete = [3]
输出：[[1,2,4]]

提示：

树中的节点数最大为 1000。
每个节点都有一个介于 1 到 1000 之间的值，且各不相同。
to_delete.length <= 1000
to_delete 包含一些从 1 到 1000、各不相同的值。

方法一：DFS · Go 实现

思考

删除若干结点后，原树裂成森林；新根是「自身未删，且父结点被删（或本为原根）」的结点。后序 DFS 先处理完左右子树，再决定当前结点是否删除：若删除，则仍然存活的孩子各自成为新树的根。

待删集合放入哈希表，判断为期望常数时间。根若未被删除，最后再加入答案。

我们先用哈希表或者一个长度为 $1001$ 的数组 $s$ 记录所有需要删除的节点。

接下来，设计一个函数 $d f s (r o o t)$ ，它会返回以 $r o o t$ 为根的子树中，删除所有需要删除的节点后的树的根节点。函数 $d f s (r o o t)$ 的执行逻辑如下：

如果 $r o o t$ 为空，那么我们返回空；
否则，我们递归执行 $d f s (r o o t . l e f t)$ 和 $d f s (r o o t . r i g h t)$ ，并将返回值分别赋给 $r o o t . l e f t$ 和 $r o o t . r i g h t$ 。如果 $r o o t$ 不需要被删除，那么我们返回 $r o o t$ ；如果 $r o o t$ 需要被删除，那么我们分别判断 $r o o t . l e f t$ 和 $r o o t . r i g h t$ 是否为空，如果它们不为空，那么我们将它们加入答案数组中；最后返回空。

在主函数中，我们调用 $d f s (r o o t)$ ，如果结果不为空，说明根节点不需要被删除，我们再将根节点加入答案数组中。最后返回答案数组即可。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 是树的节点数。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func delNodes(root *TreeNode, to_delete []int) (ans []*TreeNode) {
	s := make([]bool, 1001)
	for _, x := range to_delete {
		s[x] = true
	}
	var dfs func(*TreeNode) *TreeNode
	dfs = func(root *TreeNode) *TreeNode {
		if root == nil {
			return nil
		}
		root.Left = dfs(root.Left)
		root.Right = dfs(root.Right)
		if !s[root.Val] {
			return root
		}
		if root.Left != nil {
			ans = append(ans, root.Left)
		}
		if root.Right != nil {
			ans = append(ans, root.Right)
		}
		return nil
	}
	if dfs(root) != nil {
		ans = append(ans, root)
	}
	return
}

力扣原题 · Doocs 题解来源

1120. 子树的最大平均值 🔒

中等1 种解法

标签：树、深度优先搜索、二叉树

题目、示例与约束

给你一棵二叉树的根节点 root，找出这棵树的 每一棵 子树的 平均值 中的最大值。

子树是树中的任意节点和它的所有后代构成的集合。

树的平均值是树中节点值的总和除以节点数。

示例：

输入：[5,6,1]
输出：6.00000
解释： 
以 value = 5 的节点作为子树的根节点，得到的平均值为 (5 + 6 + 1) / 3 = 4。
以 value = 6 的节点作为子树的根节点，得到的平均值为 6 / 1 = 6。
以 value = 1 的节点作为子树的根节点，得到的平均值为 1 / 1 = 1。
所以答案取最大值 6。

提示：

树中的节点数介于 1 到 5000之间。
每个节点的值介于 0 到 100000 之间。
如果结果与标准答案的误差不超过 10^-5，那么该结果将被视为正确答案。

方法一：递归 · Go 实现

思考

子树平均值依赖该子树的结点之和与结点数，二者都需自底向上汇总。若对每个结点再扫一遍子树，总时间达平方级。

一次后序 DFS 返回 $(和, 个数)$ ，当前结点的平均值即可当场更新全局答案，再把二者交给父结点。整棵树只遍历一次。

我们可以使用递归的方法，对于每个节点，计算以该节点为根的子树的节点和以及节点个数，然后计算平均值，与当前最大值比较，更新最大值。

因此，我们设计一个函数 $d f s (r o o t)$ ，表示以 $r o o t$ 为根的子树的节点和以及节点个数，返回值为一个长度为 $2$ 的数组，其中第一个元素表示节点和，第二个元素表示节点个数。

函数 $d f s (r o o t)$ 的递归过程如下：

如果 $r o o t$ 为空，返回 $[0, 0]$ ；
否则，计算 $r o o t$ 的左子树的节点和以及节点个数，记为 $[l s, l n]$ ；计算 $r o o t$ 的右子树的节点和以及节点个数，记为 $[r s, r n]$ 。那么以 $r o o t$ 为根的子树的节点和为 $r o o t . v a l + l s + r s$ ，节点个数为 $1 + l n + r n$ ，计算平均值，与当前最大值比较，更新最大值；
返回 $[r o o t . v a l + l s + r s, 1 + l n + r n]$ 。

最后，返回最大值即可。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 为二叉树的节点个数。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func maximumAverageSubtree(root *TreeNode) (ans float64) {
	var dfs func(*TreeNode) [2]int
	dfs = func(root *TreeNode) [2]int {
		if root == nil {
			return [2]int{}
		}
		l, r := dfs(root.Left), dfs(root.Right)
		s := root.Val + l[0] + r[0]
		n := 1 + l[1] + r[1]
		ans = math.Max(ans, float64(s)/float64(n))
		return [2]int{s, n}
	}
	dfs(root)
	return
}

力扣原题 · Doocs 题解来源

1123. 最深叶节点的最近公共祖先

中等1 种解法

标签：树、深度优先搜索、广度优先搜索、哈希表、二叉树、最近公共祖先、树形 DP

题目、示例与约束

给你一个有根节点 root 的二叉树，返回它 最深的叶节点的最近公共祖先 。

回想一下：

叶节点 是二叉树中没有子节点的节点
树的根节点的深度为 0，如果某一节点的深度为 d，那它的子节点的深度就是 d+1
如果我们假定 A 是一组节点 S 的 最近公共祖先，S 中的每个节点都在以 A 为根节点的子树中，且 A 的深度达到此条件下可能的最大值。

示例 1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4]
输出：[2,7,4]
解释：我们返回值为 2 的节点，在图中用黄色标记。
在图中用蓝色标记的是树的最深的节点。
注意，节点 6、0 和 8 也是叶节点，但是它们的深度是 2 ，而节点 7 和 4 的深度是 3 。

示例 2：

输入：root = [1]
输出：[1]
解释：根节点是树中最深的节点，它是它本身的最近公共祖先。

示例 3：

输入：root = [0,1,3,null,2]
输出：[2]
解释：树中最深的叶节点是 2 ，最近公共祖先是它自己。

提示：

树中的节点数将在 [1, 1000] 的范围内。
0 <= Node.val <= 1000
每个节点的值都是 独一无二 的。

注意：本题与力扣 865 重复：https://leetcode.cn/problems/smallest-subtree-with-all-the-deepest-nodes/

方法一：DFS · Go 实现

思考

最深叶的 LCA 由左右子树的深度关系决定：较深一侧的答案仍在该侧；两侧深度相同则当前结点即为 LCA。一次后序 DFS 同时返回「该子树最深叶的 LCA」与「深度」，比较左右深度即可上推，无需先找齐最深叶再另求 LCA。

我们设计一个函数 $d f s (r o o t)$ ，它将返回一个二元组 $(l, d)$ ，其中 $l$ 是节点 $r o o t$ 的最深公共祖先，而 $d$ 是节点 $r o o t$ 的深度。函数 $d f s (r o o t)$ 的执行逻辑如下：

如果 $r o o t$ 为空，则返回二元组 $(N o n e, 0)$ ；
否则，我们递归调用 $d f s (r o o t . l e f t)$ 和 $d f s (r o o t . r i g h t)$ ，得到二元组 $(l, d_{1})$ 和 $(r, d_{2})$ 。如果 $d_{1} > d_{2}$ ，则 $r o o t$ 的最深公共祖先节点为 $l$ ，深度为 $d_{1} + 1$ ；如果 $d_{1} < d_{2}$ ，则 $r o o t$ 的最深公共祖先节点为 $r$ ，深度为 $d_{2} + 1$ ；如果 $d_{1} = d_{2}$ ，则 $r o o t$ 的最深公共祖先节点为 $r o o t$ ，深度为 $d_{1} + 1$ 。

我们在主函数中调用 $d f s (r o o t)$ ，并返回其返回值的第一个元素，即可得到最深公共祖先节点。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 是二叉树的节点数。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
type pair struct {
	first  *TreeNode
	second int
}

func lcaDeepestLeaves(root *TreeNode) *TreeNode {
	var dfs func(root *TreeNode) pair
	dfs = func(root *TreeNode) pair {
		if root == nil {
			return pair{nil, 0}
		}
		l, r := dfs(root.Left), dfs(root.Right)
		d1, d2 := l.second, r.second
		if d1 > d2 {
			return pair{l.first, d1 + 1}
		}
		if d1 < d2 {
			return pair{r.first, d2 + 1}
		}
		return pair{root, d1 + 1}
	}
	return dfs(root).first
}

力扣原题 · Doocs 题解来源

1145. 二叉树着色游戏

中等1 种解法

标签：树、深度优先搜索、二叉树

题目、示例与约束

有两位极客玩家参与了一场「二叉树着色」的游戏。游戏中，给出二叉树的根节点 root，树上总共有 n 个节点，且 n 为奇数，其中每个节点上的值从 1 到 n 各不相同。

最开始时：

「一号」玩家从 [1, n] 中取一个值 x（1 <= x <= n）；
「二号」玩家也从 [1, n] 中取一个值 y（1 <= y <= n）且 y != x。

「一号」玩家给值为 x 的节点染上红色，而「二号」玩家给值为 y 的节点染上蓝色。

之后两位玩家轮流进行操作，「一号」玩家先手。每一回合，玩家选择一个被他染过色的节点，将所选节点一个 未着色 的邻节点（即左右子节点、或父节点）进行染色（「一号」玩家染红色，「二号」玩家染蓝色）。

如果（且仅在此种情况下）当前玩家无法找到这样的节点来染色时，其回合就会被跳过。

若两个玩家都没有可以染色的节点时，游戏结束。着色节点最多的那位玩家获得胜利 ✌️。

现在，假设你是「二号」玩家，根据所给出的输入，假如存在一个 y 值可以确保你赢得这场游戏，则返回 true ；若无法获胜，就请返回 false 。

示例 1 ：

输入：root = [1,2,3,4,5,6,7,8,9,10,11], n = 11, x = 3
输出：true
解释：第二个玩家可以选择值为 2 的节点。

示例 2 ：

输入：root = [1,2,3], n = 3, x = 1
输出：false

提示：

树中节点数目为 n
1 <= x <= n <= 100
n 是奇数
1 <= Node.val <= n
树中所有值 互不相同

方法一：DFS · Go 实现

思考

先手占据 $x$ 后，树被分成左子树、右子树与父方向三块。后手只需选三块中最大一块的根着色，即可独占该块。若这块结点数超过 $n / 2$ ，后手必胜。找到 $x$ 后统计左右子树大小即可得到三块人数。

我们先通过 $D F S$ ，找到「一号」玩家着色点 $x$ 所在的节点，记为 $n o d e$ 。

接下来，我们统计 $n o d e$ 的左子树、右子树的节点个数，分别记为 $l$ 和 $r$ ，而 $n o d e$ 父节点方向上的个数为 $n - l - r - 1$ 。只要满足 $max (l, r, n - l - r - 1) > \frac{n}{2}$ ，则「二号」玩家存在一个必胜策略。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 是节点总数。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func btreeGameWinningMove(root *TreeNode, n int, x int) bool {
	var dfs func(*TreeNode) *TreeNode
	dfs = func(root *TreeNode) *TreeNode {
		if root == nil || root.Val == x {
			return root
		}
		node := dfs(root.Left)
		if node != nil {
			return node
		}
		return dfs(root.Right)
	}

	var count func(*TreeNode) int
	count = func(root *TreeNode) int {
		if root == nil {
			return 0
		}
		return 1 + count(root.Left) + count(root.Right)
	}

	node := dfs(root)
	l, r := count(node.Left), count(node.Right)
	return max(max(l, r), n-l-r-1) > n/2
}

力扣原题 · Doocs 题解来源

1161. 最大层内元素和

中等2 种解法

标签：树、深度优先搜索、广度优先搜索、二叉树

题目、示例与约束

给你一个二叉树的根节点 root。设根节点位于二叉树的第 1 层，而根节点的子节点位于第 2 层，依此类推。

返回总和最大的那一层的层号 x。如果有多层的总和一样大，返回其中最小的层号 x。

示例 1：

输入：root = [1,7,0,7,-8,null,null]
输出：2
解释：
第 1 层各元素之和为 1，
第 2 层各元素之和为 7 + 0 = 7，
第 3 层各元素之和为 7 + -8 = -1，
所以我们返回第 2 层的层号，它的层内元素之和最大。

示例 2：

输入：root = [989,null,10250,98693,-89388,null,null,null,-32127]
输出：2

提示：

树中的节点数在 [1, 10⁴]范围内
-10⁵ <= Node.val <= 10⁵

方法一：BFS · Go 实现

思考

层号与层和天然对应层次遍历。BFS 按层取出当前队列中的全部结点并求和，同时记下更大层和对应的层号；和相等时不更新，从而保留较小层号。整棵树访问一次。

BFS 层次遍历，求每一层的节点和，找出节点和最大的层，若有多个层的节点和最大，则返回最小的层。

具体地，我们使用一个队列 $q$ 来存储当前层的节点。每次遍历时，我们记录当前层的节点和 $s$ ，然后将当前层的所有节点的子节点加入队列中，准备遍历下一层。我们使用变量 $m x$ 来记录当前最大的节点和，使用变量 $a n s$ 来记录对应的层号。每次计算完一层的节点和后，如果 $s$ 大于 $m x$ ，则更新 $m x$ 和 $a n s$ 。最后返回 $a n s$ 即可。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 为二叉树的节点数。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func maxLevelSum(root *TreeNode) int {
	q := []*TreeNode{root}
	mx := -0x3f3f3f3f
	i := 0
	ans := 0
	for len(q) > 0 {
		i++
		s := 0
		for n := len(q); n > 0; n-- {
			root = q[0]
			q = q[1:]
			s += root.Val
			if root.Left != nil {
				q = append(q, root.Left)
			}
			if root.Right != nil {
				q = append(q, root.Right)
			}
		}
		if mx < s {
			mx = s
			ans = i
		}
	}
	return ans
}

方法二：DFS · Go 实现

思考

方法一需要队列存放整层结点。DFS 用数组 $s [i]$ 累加深度 $i$ 的结点值，递归栈只与树高有关。最后在 $s$ 上取最大和的最小下标，语义与 BFS 相同。

我们也可以使用 DFS 求解。我们用一个数组 $s$ 来存储每一层的节点和，数组的下标表示层数，数组的值表示节点和。我们使用 DFS 遍历二叉树，将每个节点的值加到对应层数的节点和上。最后，我们返回 $s$ 中的最大值对应的下标即可。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 为二叉树的节点数。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func maxLevelSum(root *TreeNode) int {
	s := []int{}
	var dfs func(*TreeNode, int)
	dfs = func(root *TreeNode, i int) {
		if root == nil {
			return
		}
		if len(s) == i {
			s = append(s, root.Val)
		} else {
			s[i] += root.Val
		}
		dfs(root.Left, i+1)
		dfs(root.Right, i+1)
	}
	dfs(root, 0)
	ans, mx := 0, -0x3f3f3f3f
	for i, v := range s {
		if mx < v {
			mx = v
			ans = i + 1
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

LeetCode Go · 树与二叉树（4） ​

814. 二叉树剪枝 ​

863. 二叉树中所有距离为 K 的结点 ​

865. 具有所有最深节点的最小子树 ​

872. 叶子相似的树 ​

889. 从前序与后序遍历序列构造二叉树 ​

894. 所有可能的真二叉树 ​

897. 递增顺序搜索树 ​

938. 二叉搜索树的范围和 ​

951. 翻转等价二叉树 ​

958. 二叉树的完全性检验 ​

965. 单值二叉树 ​

968. 监控二叉树 ​

971. 翻转二叉树以匹配先序遍历 ​

979. 在二叉树中分配硬币 ​

987. 二叉树的垂序遍历 ​

988. 从叶结点开始的最小字符串 ​

993. 二叉树的堂兄弟节点 ​

998. 最大二叉树 II ​

1008. 前序遍历构造二叉搜索树 ​

1022. 从根到叶的二进制数之和 ​

1026. 节点与其祖先之间的最大差值 ​

1028. 从先序遍历还原二叉树 ​

1038. 从二叉搜索树到更大和树 ​

1080. 根到叶路径上的不足节点 ​

1104. 二叉树寻路 ​

1110. 删点成林 ​

1120. 子树的最大平均值 🔒 ​

1123. 最深叶节点的最近公共祖先 ​

1145. 二叉树着色游戏 ​

1161. 最大层内元素和 ​

继续阅读

LeetCode Go · 树与二叉树（4）

814. 二叉树剪枝

863. 二叉树中所有距离为 K 的结点

865. 具有所有最深节点的最小子树

872. 叶子相似的树

889. 从前序与后序遍历序列构造二叉树

894. 所有可能的真二叉树

897. 递增顺序搜索树

938. 二叉搜索树的范围和

951. 翻转等价二叉树

958. 二叉树的完全性检验

965. 单值二叉树

968. 监控二叉树

971. 翻转二叉树以匹配先序遍历

979. 在二叉树中分配硬币

987. 二叉树的垂序遍历

988. 从叶结点开始的最小字符串

993. 二叉树的堂兄弟节点

998. 最大二叉树 II

1008. 前序遍历构造二叉搜索树

1022. 从根到叶的二进制数之和

1026. 节点与其祖先之间的最大差值

1028. 从先序遍历还原二叉树

1038. 从二叉搜索树到更大和树

1080. 根到叶路径上的不足节点

1104. 二叉树寻路

1110. 删点成林

1120. 子树的最大平均值 🔒

1123. 最深叶节点的最近公共祖先

1145. 二叉树着色游戏

1161. 最大层内元素和