LeetCode Go · 树与二叉树（2）

来源与许可

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

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

230. 二叉搜索树中第 K 小的元素

中等2 种解法

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

题目、示例与约束

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（k 从 1 开始计数）。

示例 1：

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

示例 2：

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

提示：

树中的节点数为 n 。
1 <= k <= n <= 10⁴
0 <= Node.val <= 10⁴

进阶：如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化算法？

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

思考

BST 的中序遍历即为升序。只需走到第 $k$ 个被访问的结点，不必列出整棵树。

用栈模拟一路向左，弹出时将 $k$ 减一，减到 $0$ 即答案。

由于二叉搜索树的性质，中序遍历一定能得到升序序列，因此可以采用中序遍历找出第 k 小的元素。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func kthSmallest(root *TreeNode, k int) int {
	stk := []*TreeNode{}
	for root != nil || len(stk) > 0 {
		if root != nil {
			stk = append(stk, root)
			root = root.Left
		} else {
			root = stk[len(stk)-1]
			stk = stk[:len(stk)-1]
			k--
			if k == 0 {
				return root.Val
			}
			root = root.Right
		}
	}
	return 0
}

方法二：预处理结点数 · Go 实现

思考

单次中序已够，但若反复查询而树不变，每次 $O (h + k)$ 仍重复走左链。预处理每棵子树的结点数后，可比较左子树规模与 $k$ 决定向左或向右。

一次查询变为沿根下行，适合静态树上的多次询问。

预处理每个结点作为根节点的子树的节点数。

这种算法可以用来优化频繁查找第 k 个树、而二叉搜索树本身不被修改的情况。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
type BST struct {
	cnt  map[*TreeNode]int
	root *TreeNode
}

func newBST(root *TreeNode) *BST {
	var count func(*TreeNode) int
	cnt := map[*TreeNode]int{}
	count = func(root *TreeNode) int {
		if root == nil {
			return 0
		}
		n := 1 + count(root.Left) + count(root.Right)
		cnt[root] = n
		return n
	}
	count(root)
	return &BST{cnt, root}
}

func (bst *BST) kthSmallest(k int) int {
	node := bst.root
	for node != nil {
		v := 0
		if node.Left != nil {
			v = bst.cnt[node.Left]
		}
		if v == k-1 {
			return node.Val
		}
		if v < k-1 {
			k -= (v + 1)
			node = node.Right
		} else {
			node = node.Left
		}
	}
	return 0
}

func kthSmallest(root *TreeNode, k int) int {
	bst := newBST(root)
	return bst.kthSmallest(k)
}

力扣原题 · Doocs 题解来源

235. 二叉搜索树的最近公共祖先

中等2 种解法

标签：树、深度优先搜索、二叉搜索树、二叉树、最近公共祖先

题目、示例与约束

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉搜索树: 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, 因为根据定义最近公共祖先节点可以为节点本身。

说明:

所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉搜索树中。

方法一：迭代 · Go 实现

思考

BST 上 $p, q$ 的 LCA 必落在二者值之间的分岔点。从根下行：二者都小于当前结点则走左，都大于则走右，否则当前即为分岔。

迭代即可，无需递归栈。

我们从根节点开始遍历，如果当前节点的值小于 $p$ 和 $q$ 的值，说明 $p$ 和 $q$ 应该在当前节点的右子树，因此将当前节点移动到右子节点；如果当前节点的值大于 $p$ 和 $q$ 的值，说明 $p$ 和 $q$ 应该在当前节点的左子树，因此将当前节点移动到左子节点；否则说明当前节点就是 $p$ 和 $q$ 的最近公共祖先，返回当前节点即可。

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

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

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	for {
		if root.Val < min(p.Val, q.Val) {
			root = root.Right
		} else if root.Val > max(p.Val, q.Val) {
			root = root.Left
		} else {
			return root
		}
	}
}

方法二：递归 · Go 实现

思考

同一分岔规则也可写成递归：若 $p, q$ 都在左（或右）则递归该侧，否则返回当前根。逻辑与迭代相同，实现更短。

我们也可以使用递归的方法来解决这个问题。

我们首先判断当前节点的值是否小于 $p$ 和 $q$ 的值，如果是，则递归遍历右子树；如果当前节点的值大于 $p$ 和 $q$ 的值，如果是，则递归遍历左子树；否则说明当前节点就是 $p$ 和 $q$ 的最近公共祖先，返回当前节点即可。

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

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

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	if root.Val < p.Val && root.Val < q.Val {
		return lowestCommonAncestor(root.Right, p, q)
	}
	if root.Val > p.Val && root.Val > q.Val {
		return lowestCommonAncestor(root.Left, p, q)
	}
	return root
}

力扣原题 · Doocs 题解来源

236. 二叉树的最近公共祖先

中等1 种解法

标签：树、深度优先搜索、二叉树、最近公共祖先

题目、示例与约束

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例 1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

示例 2：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3：

输入：root = [1,2], p = 1, q = 2
输出：1

提示：

树中节点数目在范围 [2, 10⁵] 内。
-10⁹ <= Node.val <= 10⁹
所有 Node.val 互不相同 。
p != q
p 和 q 均存在于给定的二叉树中。

方法一：递归 · Go 实现

思考

普通二叉树没有有序性，不能按值决定方向。LCA 是同时覆盖 $p$ 与 $q$ 的最深结点。

后序递归：子树中找到目标则上送该结点；左右都非空则当前根为 LCA，否则上送非空一侧。

我们递归遍历二叉树：

如果当前节点为空或者等于 $p$ 或者 $q$ ，则返回当前节点；

否则，我们递归遍历左右子树，将返回的结果分别记为 $l e f t$ 和 $r i g h t$ 。如果 $l e f t$ 和 $r i g h t$ 都不为空，则说明 $p$ 和 $q$ 分别在左右子树中，因此当前节点即为最近公共祖先；如果 $l e f 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 lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	if root == nil || root == p || root == q {
		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
}

力扣原题 · Doocs 题解来源

250. 统计同值子树 🔒

中等1 种解法

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

题目、示例与约束

给定一个二叉树，统计该二叉树数值相同的子树个数。

同值子树是指该子树的所有节点都拥有相同的数值。

示例 1：

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

示例 2：

输入：root = []
输出：0

示例 3：

输入：root = [5,5,5,5,5,null,5]
输出：6

提示：

树中节点的编号在 [0, 1000] 范围内
-1000 <= Node.val <= 1000

方法一：递归 · Go 实现

思考

一棵子树是单值，当且仅当左右子树都是单值且根值与孩子相同。自底向上一次遍历即可计数。

$d f s$ 返回该子树是否单值：左右皆真且两侧值（空则视作根值）等于根时，答案加一并返回真。

我们设计一个递归函数 $d f s (r o o t)$ ，该函数返回以 $r o o t$ 为根的子树中所有节点的值是否相同。

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

如果 $r o o t$ 为空，则返回 true；
否则，我们递归地计算 $r o o t$ 的左右子树，记为 $l$ 和 $r$ ；如果 $l$ 为 false 或者 $r$ 为 false，则返回 false；如果 $r o o t$ 的左子树不为空且 $r o o t$ 的左子树的值不等于 $r o o t$ 的值，或者 $r o o t$ 的右子树不为空且 $r o o t$ 的右子树的值不等于 $r o o t$ 的值，则返回 false；否则，我们将答案加一，并返回 true。

递归结束后，返回答案即可。

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

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func countUnivalSubtrees(root *TreeNode) (ans int) {
	var dfs func(*TreeNode) bool
	dfs = func(root *TreeNode) bool {
		if root == nil {
			return true
		}
		l, r := dfs(root.Left), dfs(root.Right)
		if !l || !r {
			return false
		}
		if root.Left != nil && root.Left.Val != root.Val {
			return false
		}
		if root.Right != nil && root.Right.Val != root.Val {
			return false
		}
		ans++
		return true
	}
	dfs(root)
	return
}

力扣原题 · Doocs 题解来源

255. 验证二叉搜索树的前序遍历序列 🔒

中等1 种解法

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

题目、示例与约束

给定一个 无重复元素 的整数数组 preorder ， 如果它是以二叉搜索树的先序遍历排列 ，返回 true 。

示例 1：

输入: preorder = [5,2,1,3,6]
输出: true

示例 2：

输入: preorder = [5,2,6,1,3]
输出: false

提示:

1 <= preorder.length <= 10⁴
1 <= preorder[i] <= 10⁴
preorder 中 无重复元素

进阶：您能否使用恒定的空间复杂度来完成此题？

方法一 · Go 实现

思考

重建整棵 BST 再验证偏重。先序先访问根、再左、后右，栈中递减的是尚未转向右子树的结点。

当前值小于已弹出的下界则违反 BST；否则弹出所有小于它的栈顶作为新下界，再压入当前值。

func verifyPreorder(preorder []int) bool {
	var stk []int
	last := math.MinInt32
	for _, x := range preorder {
		if x < last {
			return false
		}
		for len(stk) > 0 && stk[len(stk)-1] < x {
			last = stk[len(stk)-1]
			stk = stk[0 : len(stk)-1]
		}
		stk = append(stk, x)
	}
	return true
}

力扣原题 · Doocs 题解来源

257. 二叉树的所有路径

简单1 种解法

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

题目、示例与约束

给你一个二叉树的根节点 root。

按 任意顺序 ，返回所有 从根节点到叶子节点 的路径。

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

示例 1：

输入：root = [1,2,3,null,5]
输出：["1->2->5","1->3"]

示例 2：

输入：root = [1]
输出：["1"]

提示：

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

方法一：DFS · Go 实现

思考

根到叶的路径需在遍历时记下沿途结点。DFS 下行时把当前值加入路径，到达叶子则拼接进答案，返回时弹出以回溯。

我们可以使用深度优先搜索的方法遍历整棵二叉树，每一次我们将当前的节点添加到路径中。如果当前的节点是叶子节点，则我们将整个路径加入到答案中。否则我们继续递归遍历节点的孩子节点。最后当我们递归结束返回到当前节点时，我们需要将当前节点从路径中删除。

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

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func binaryTreePaths(root *TreeNode) (ans []string) {
	t := []string{}
	var dfs func(*TreeNode)
	dfs = func(root *TreeNode) {
		if root == nil {
			return
		}
		t = append(t, strconv.Itoa(root.Val))
		if root.Left == nil && root.Right == nil {
			ans = append(ans, strings.Join(t, "->"))
		} else {
			dfs(root.Left)
			dfs(root.Right)
		}
		t = t[:len(t)-1]
	}
	dfs(root)
	return
}

力扣原题 · Doocs 题解来源

270. 最接近的二叉搜索树值 🔒

简单2 种解法

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

题目、示例与约束

给你二叉搜索树的根节点 root 和一个目标值 target ，请在该二叉搜索树中找到最接近目标值 target 的数值。如果有多个答案，返回最小的那个。

示例 1：

输入：root = [4,2,5,1,3], target = 3.714286
输出：4

示例 2：

输入：root = [1], target = 4.428571
输出：1

提示：

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

方法一：递归 · Go 实现

思考

不必遍历整棵 BST：与 $t a r g e t$ 比较后只走一侧。沿路更新与 $t a r g e t$ 更近（并列取较小）的答案。

递归沿左或右下行即可。

我们定义一个递归函数 $dfs (n o d e)$ ，表示从当前节点 $n o d e$ 开始，寻找最接近目标值 $t a r g e t$ 的节点。我们可以通过比较当前节点的值与目标值的差的绝对值，来更新答案，如果目标值小于当前节点的值，我们就递归地搜索左子树，否则我们递归地搜索右子树。

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

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func closestValue(root *TreeNode, target float64) int {
	ans := root.Val
	diff := math.MaxFloat64
	var dfs func(*TreeNode)
	dfs = func(node *TreeNode) {
		if node == nil {
			return
		}
		nxt := math.Abs(float64(node.Val) - target)
		if nxt < diff || (nxt == diff && node.Val < ans) {
			diff = nxt
			ans = node.Val
		}
		if target < float64(node.Val) {
			dfs(node.Left)
		} else {
			dfs(node.Right)
		}
	}
	dfs(root)
	return ans
}

方法二：迭代 · Go 实现

思考

同一路径可用迭代实现，去掉递归栈，空间降为常数。

我们可以将递归函数改写为迭代的形式，使用一个循环来模拟递归的过程。我们从根节点开始，判断当前节点的值与目标值的差的绝对值是否小于当前的最小差，如果是，我们就更新答案。然后根据目标值与当前节点的值的大小关系，决定向左子树还是右子树移动。当我们遍历到空节点时，循环结束。

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

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func closestValue(root *TreeNode, target float64) int {
	ans := root.Val
	diff := math.MaxFloat64
	for root != nil {
		nxt := math.Abs(float64(root.Val) - target)
		if nxt < diff || (nxt == diff && root.Val < ans) {
			diff = nxt
			ans = root.Val
		}
		if float64(root.Val) > target {
			root = root.Left
		} else {
			root = root.Right
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

272. 最接近的二叉搜索树值 II 🔒

困难1 种解法

标签：栈、树、深度优先搜索、二叉搜索树、双指针、二叉树、堆（优先队列）

题目、示例与约束

给定二叉搜索树的根 root 、一个目标值 target 和一个整数 k ，返回BST中最接近目标的 k 个值。你可以按 任意顺序 返回答案。

题目保证该二叉搜索树中只会存在一种 k 个值集合最接近 target

示例 1：

输入: root = [4,2,5,1,3]，目标值 = 3.714286，且 k = 2
输出: [4,3]

示例 2:

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

提示：

二叉树的节点总数为 n
1 <= k <= n <= 10⁴
0 <= Node.val <= 10⁹
-10⁹ <= target <= 10⁹

进阶：假设该二叉搜索树是平衡的，请问您是否能在小于 O(n)（ n = total nodes ）的时间复杂度内解决该问题呢？

方法一 · Go 实现

思考

BST 中序为有序序列，与 $t a r g e t$ 最近的 $k$ 个数在该序列上构成一段窗口。维护长度为 $k$ 的队列，中序填入。

窗口已满且当前值不再更近时，右侧只会更远，可以剪枝返回。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func closestKValues(root *TreeNode, target float64, k int) []int {
	var ans []int
	var dfs func(root *TreeNode)
	dfs = func(root *TreeNode) {
		if root == nil {
			return
		}
		dfs(root.Left)
		if len(ans) < k {
			ans = append(ans, root.Val)
		} else {
			if math.Abs(float64(root.Val)-target) >= math.Abs(float64(ans[0])-target) {
				return
			}
			ans = ans[1:]
			ans = append(ans, root.Val)
		}
		dfs(root.Right)
	}
	dfs(root)
	return ans
}

力扣原题 · Doocs 题解来源

285. 二叉搜索树中的中序后继 🔒

中等1 种解法

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

题目、示例与约束

给定一棵二叉搜索树和其中的一个节点 p ，找到该节点在树中的中序后继。如果节点没有中序后继，请返回 null 。

节点 p 的后继是值比 p.val 大的节点中键值最小的节点。

示例 1：

输入：root = [2,1,3], p = 1
输出：2
解释：这里 1 的中序后继是 2。请注意 p 和返回值都应是 TreeNode 类型。

示例 2：

输入：root = [5,3,6,2,4,null,null,1], p = 6
输出：null
解释：因为给出的节点没有中序后继，所以答案就返回 null 了。

提示：

树中节点的数目在范围 [1, 10⁴] 内。
-10⁵ <= Node.val <= 10⁵
树中各节点的值均保证唯一。

方法一：二分搜索 · Go 实现

思考

中序后继是值大于 $p$ 的最小结点。BST 上可像二分一样走：当前值大于 $p$ 则它是候选并转向左，否则转向右。

走完整条路径后记下的候选即为后继，高度时间内完成。

二叉搜索树的中序遍历是一个升序序列，因此可以使用二分搜索的方法。

二叉搜索树节点 $p$ 的中序后继节点满足：

中序后继的节点值大于 $p$ 的节点值
中序后继是所有大于 $p$ 的节点中值最小的节点

因此，对于当前节点 $r o o t$ ，如果 $r o o t . v a l > p . v a l$ ，则 $r o o t$ 可能是 $p$ 的中序后继节点，将 $r o o t$ 记为 $a n s$ ，然后搜索左子树，即 $r o o t = r o o t . l e f t$ ；如果 $r o o t . v a l \leq p . v a l$ ，则 $r o o t$ 不能是 $p$ 的中序后继节点，搜索右子树，即 $r o o t = r o o t . r i g h t$ 。

时间复杂度 $O (h)$ ，其中 $h$ 为二叉搜索树的高度。空间复杂度 $O (1)$ 。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderSuccessor(root *TreeNode, p *TreeNode) (ans *TreeNode) {
	for root != nil {
		if root.Val > p.Val {
			ans = root
			root = root.Left
		} else {
			root = root.Right
		}
	}
	return
}

力扣原题 · Doocs 题解来源

298. 二叉树最长连续序列 🔒

中等1 种解法

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

题目、示例与约束

给你一棵指定的二叉树的根节点 root ，请你计算其中 最长连续序列路径 的长度。

最长连续序列路径 是依次递增 1 的路径。该路径，可以是从某个初始节点到树中任意节点，通过「父 - 子」关系连接而产生的任意路径。且必须从父节点到子节点，反过来是不可以的。

示例 1：

输入：root = [1,null,3,2,4,null,null,null,5]
输出：3
解释：当中，最长连续序列是 3-4-5 ，所以返回结果为 3 。

示例 2：

输入：root = [2,null,3,2,null,1]
输出：2
解释：当中，最长连续序列是 2-3 。注意，不是 3-2-1，所以返回 2 。

提示：

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

方法一：DFS · Go 实现

思考

连续路径是父到子相差 $1$ 的下行链。后序得到左右连续长度，仅当孩子值恰好比根大 $1$ 时才能接上，否则从本结点重新计 $1$ 。

$d f s$ 返回以当前结点开头的最长连续长度，并全局更新答案。

我们设计一个函数 $d f s (r o o t)$ ，表示以 $r o o t$ 为连续序列的第一个节点的最长连续序列路径长度。

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

如果 $r o o t$ 为空，那么返回 $0$ 。

否则，我们递归计算 $r o o t$ 的左右子节点，分别得到 $l$ 和 $r$ ，如果 $r o o t$ 的左子节点和 $r o o t$ 连续，那么 $l$ 的值加 $1$ ，否则置 $l$ 为 $1$ ；如果 $r o o t$ 的右子节点和 $r o o t$ 连续，那么 $r$ 的值加 $1$ ，否则置 $r$ 为 $1$ 。

然后我们更新答案为 $a n s = max (a n s, l, r)$ ，并返回 $max (l, r)$ 。

最后，我们调用 $d f s (r o o t)$ ，返回答案 $a n s$ 。

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

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func longestConsecutive(root *TreeNode) (ans int) {
	var dfs func(*TreeNode) int
	dfs = func(root *TreeNode) int {
		if root == nil {
			return 0
		}
		l := dfs(root.Left) + 1
		r := dfs(root.Right) + 1
		if root.Left != nil && root.Left.Val-root.Val != 1 {
			l = 1
		}
		if root.Right != nil && root.Right.Val-root.Val != 1 {
			r = 1
		}
		t := max(l, r)
		ans = max(ans, t)
		return t
	}
	dfs(root)
	return
}

力扣原题 · Doocs 题解来源

314. 二叉树的垂直遍历 🔒

中等2 种解法

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

题目、示例与约束

给你一个二叉树的根结点，返回其结点按 垂直方向（从上到下，逐列）遍历的结果。

如果两个结点在同一行和列，那么顺序则为 从左到右。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[9],[3,15],[20],[7]]

示例 2：

输入：root = [3,9,8,4,0,1,7]
输出：[[4],[9],[3,0,1],[8],[7]]

示例 3：

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

提示：

树中结点的数目在范围 [0, 100] 内
-100 <= Node.val <= 100

方法一：DFS · Go 实现

思考

竖直遍历按列从左到右、列内从上到下输出。DFS 访问顺序并非层序，同一列可能先深后浅。

为此在递归中记录深度与横向偏移，按列分桶后再按深度排序。列键排序保证从左到右。

DFS 遍历二叉树，记录每个节点的值、深度，以及横向的偏移量。然后对所有节点按照横向偏移量从小到大排序，再按照深度从小到大排序，最后按照横向偏移量分组。

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

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func verticalOrder(root *TreeNode) [][]int {
	d := map[int][][]int{}
	var dfs func(*TreeNode, int, int)
	dfs = func(root *TreeNode, depth, offset int) {
		if root == nil {
			return
		}
		d[offset] = append(d[offset], []int{depth, root.Val})
		dfs(root.Left, depth+1, offset-1)
		dfs(root.Right, depth+1, offset+1)
	}
	dfs(root, 0, 0)
	idx := []int{}
	for i := range d {
		idx = append(idx, i)
	}
	sort.Ints(idx)
	ans := [][]int{}
	for _, i := range idx {
		v := d[i]
		sort.SliceStable(v, func(i, j int) bool { return v[i][0] < v[j][0] })
		t := []int{}
		for _, x := range v {
			t = append(t, x[1])
		}
		ans = append(ans, t)
	}
	return ans
}

方法二：BFS · Go 实现

思考

方法一同一列还需按深度再排序。BFS 按层推进，先入队者深度更小，列内自然有序，只需按列键排序输出。左右孩子分别带偏移 $- 1$ 、 $+ 1$ 入队。

本题较好的做法应该是 BFS，从上往下逐层进行遍历。

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

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func verticalOrder(root *TreeNode) [][]int {
	ans := [][]int{}
	if root == nil {
		return ans
	}
	d := map[int][]int{}
	q := []pair{pair{root, 0}}
	for len(q) > 0 {
		for n := len(q); n > 0; n-- {
			p := q[0]
			q = q[1:]
			root = p.node
			offset := p.offset
			d[offset] = append(d[offset], root.Val)
			if root.Left != nil {
				q = append(q, pair{root.Left, offset - 1})
			}
			if root.Right != nil {
				q = append(q, pair{root.Right, offset + 1})
			}
		}
	}
	idx := []int{}
	for i := range d {
		idx = append(idx, i)
	}
	sort.Ints(idx)
	for _, i := range idx {
		ans = append(ans, d[i])
	}
	return ans
}

type pair struct {
	node   *TreeNode
	offset int
}

力扣原题 · Doocs 题解来源

331. 验证二叉树的前序序列化

中等1 种解法

标签：栈、树、字符串、二叉树

题目、示例与约束

序列化二叉树的一种方法是使用 前序遍历 。当我们遇到一个非空节点时，我们可以记录下这个节点的值。如果它是一个空节点，我们可以使用一个标记值记录，例如 #。

例如，上面的二叉树可以被序列化为字符串 "9,3,4,#,#,1,#,#,2,#,6,#,#"，其中 # 代表一个空节点。

给定一串以逗号分隔的序列，验证它是否是正确的二叉树的前序序列化。编写一个在不重构树的条件下的可行算法。

保证每个以逗号分隔的字符或为一个整数或为一个表示 null 指针的 '#' 。

你可以认为输入格式总是有效的

例如它永远不会包含两个连续的逗号，比如 "1,,3" 。

注意：不允许重建树。

示例 1:

输入: preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#"
输出: true

示例 2:

输入: preorder = "1,#"
输出: false

示例 3:

输入: preorder = "9,#,#,1"
输出: false

提示:

1 <= preorder.length <= 10⁴
preorder 由以逗号 “，” 分隔的 [0,100] 范围内的整数和 “#” 组成

方法一：栈 · Go 实现

思考

判断逗号分隔的先序序列是否对应一棵二叉树。结点有两个孩子，空孩子为 #。计数槽位可做，也可用栈归约。

遇到 值 # # 说明一棵叶子子树已完成，将其收成一个 #。反复归约后若只剩一个 #，则整棵树合法。非空结点后必须能配上两棵子树，否则栈无法收干净。

我们将字符串 preorder 按逗号分割成数组，然后遍历数组，如果遇到了连续两个 '#'，并且第三个元素不是 '#'，那么就将这三个元素替换成一个 '#'，这个过程一直持续到数组遍历结束。

最后，判断数组长度是否为 $1$ ，且数组唯一的元素是否为 '#' 即可。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 为字符串 preorder 的长度。

func isValidSerialization(preorder string) bool {
	stk := []string{}
	for _, s := range strings.Split(preorder, ",") {
		stk = append(stk, s)
		for len(stk) >= 3 && stk[len(stk)-1] == "#" && stk[len(stk)-2] == "#" && stk[len(stk)-3] != "#" {
			stk = stk[:len(stk)-3]
			stk = append(stk, "#")
		}
	}
	return len(stk) == 1 && stk[0] == "#"
}

力扣原题 · Doocs 题解来源

333. 最大二叉搜索子树 🔒

中等1 种解法

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

题目、示例与约束

给定一个二叉树，找到其中最大的二叉搜索树（BST）子树，并返回该子树的大小。其中，最大指的是子树节点数最多的。

二叉搜索树（BST）中的所有节点都具备以下属性：

左子树的值小于其父（根）节点的值。
右子树的值大于其父（根）节点的值。

注意：子树必须包含其所有后代。

示例 1：

输入：root = [10,5,15,1,8,null,7]
输出：3
解释：本例中最大的 BST 子树是高亮显示的子树。返回值是子树的大小，即 3 。

示例 2：

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

提示：

树上节点数目的范围是 [0, 10⁴]
-10⁴ <= Node.val <= 10⁴

进阶: 你能想出 O(n) 时间复杂度的解法吗？

方法一 · Go 实现

思考

求最大二叉搜索子树的结点数。对每个结点单独验证 BST 会重复遍历。子树是否为 BST 取决于左右极值与自身大小关系。

后序返回 $(最小值, 最大值, 规模)$ 。若左最大 $<$ 根 $<$ 右最小，则合并规模并更新答案；否则返回哨兵 $(- \infty, \infty, 0)$ 使祖先无法再并入。空树返回 $(\infty, - \infty, 0)$ 以便叶子成立。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func largestBSTSubtree(root *TreeNode) int {
	ans := 0
	var dfs func(root *TreeNode) []int
	dfs = func(root *TreeNode) []int {
		if root == nil {
			return []int{math.MaxInt32, math.MinInt32, 0}
		}
		left := dfs(root.Left)
		right := dfs(root.Right)
		if left[1] < root.Val && root.Val < right[0] {
			ans = max(ans, left[2]+right[2]+1)
			return []int{min(root.Val, left[0]), max(root.Val, right[1]), left[2] + right[2] + 1}
		}
		return []int{math.MinInt32, math.MaxInt32, 0}
	}
	dfs(root)
	return ans
}

力扣原题 · Doocs 题解来源

337. 打家劫舍 III

中等1 种解法

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

题目、示例与约束

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。

除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。

给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额。

示例 1:

输入: root = [3,2,3,null,3,null,1]
输出: 7 
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7

示例 2:

输入: root = [3,4,5,1,3,null,1]
输出: 9
解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9

提示：

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

方法一：树形 DP · Go 实现

思考

树上相邻结点不能同时偷。若对每个结点分别计算「偷/不偷」再重复遍历子树，同一子树会被多次展开。

后序返回二元组：偷根、不偷根。偷根则左右只能取不偷；不偷根则左右各自取较大者。根处再取二者最大。每个结点只访问一次。

我们定义一个函数 $d f s (r o o t)$ ，表示偷取以 $r o o t$ 为根的二叉树的最大金额。该函数返回一个二元组 $(a, b)$ ，其中 $a$ 表示偷取 $r o o t$ 节点时能得到的最大金额，而 $b$ 表示不偷取 $r o o t$ 节点时能得到的最大金额。

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

如果 $r o o t$ 为空，那么显然有 $d f s (r o o t) = (0, 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_{a}, l_{b})$ 以及 $(r_{a}, r_{b})$ 。对于 $d f s (r o o t)$ 的结果，我们可以分为两种情况：

如果偷取 $r o o t$ 节点，那么不能偷取其左右子节点，结果为 $r o o t . v a l + l_{b} + r_{b}$ ；
如果不偷取 $r o o t$ 节点，那么可以偷取其左右子节点，结果为 $max (l_{a}, l_{b}) + max (r_{a}, r_{b})$ 。

在主函数中，我们可以直接返回 $d f s (r o o t)$ 的较大值，即 $max (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 rob(root *TreeNode) int {
	var dfs func(*TreeNode) (int, int)
	dfs = func(root *TreeNode) (int, int) {
		if root == nil {
			return 0, 0
		}
		la, lb := dfs(root.Left)
		ra, rb := dfs(root.Right)
		return root.Val + lb + rb, max(la, lb) + max(ra, rb)
	}
	a, b := dfs(root)
	return max(a, b)
}

力扣原题 · Doocs 题解来源

366. 寻找二叉树的叶子节点 🔒

中等1 种解法

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

题目、示例与约束

给你一棵二叉树的 root 节点，请按照以下方式收集树的节点：

收集所有的叶子节点。
移除所有的叶子节点。
重复以上步骤，直到树为空。

示例 1：

输入：root = [1,2,3,4,5]
输出：[[4,5,3],[2],[1]]
解释：
[[3,5,4],[2],[1]] 和 [[3,4,5],[2],[1]] 也被视作正确答案，因为每一层返回元素的顺序不影响结果。

示例 2：

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

提示：

树中节点的数量在[1, 100]范围内。
-100 <= Node.val <= 100

方法一：DFS · Go 实现

思考

反复摘掉当前叶子，按摘取轮次分组。模拟删除需多次遍历。结点被摘的轮次等于它到叶子的高度。

后序求高度 $h = max (左, 右)$ ，把结点放入 $a n s [h]$ ，返回 $h + 1$ 。同一高度在同一轮被摘。

我们可以使用深度优先搜索的方法，递归遍历二叉树，将每个节点的高度作为索引，将节点的值添加到对应索引的数组中。

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

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func findLeaves(root *TreeNode) (ans [][]int) {
	var dfs func(*TreeNode) int
	dfs = func(root *TreeNode) int {
		if root == nil {
			return 0
		}
		l, r := dfs(root.Left), dfs(root.Right)
		h := max(l, r)
		if len(ans) == h {
			ans = append(ans, []int{})
		}
		ans[h] = append(ans[h], root.Val)
		return h + 1
	}
	dfs(root)
	return
}

力扣原题 · Doocs 题解来源

404. 左叶子之和

简单2 种解法

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

题目、示例与约束

给定二叉树的根节点 root ，返回所有左叶子之和。

示例 1：

输入: root = [3,9,20,null,null,15,7] 
输出: 24 
解释: 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24

示例 2:

输入: root = [1]
输出: 0

提示:

节点数在 [1, 1000] 范围内
-1000 <= Node.val <= 1000

方法一：递归 · Go 实现

思考

需要把「左孩子且为叶子」与普通左子树分开。若对每个节点都再扫一遍子树，会重复访问。

一次递归即可：右子树一律下探；左孩子若无子女则累加其值，否则继续递归。空树返回 $0$ 。判定叶子用左右指针同为空，避免额外遍历。

我们首先判断 root 是否为空，如果为空则返回 $0$ 。

否则，我们递归调用 sumOfLeftLeaves 函数计算 root 的右子树中所有左叶子之和，并将结果赋给答案变量 $a n s$ 。然后我们判断 root 的左子节点是否存在，如果存在，我们判断其是否为叶子节点，如果是叶子节点，则将其值加到答案变量 $a n s$ 中，否则我们递归调用 sumOfLeftLeaves 函数计算 root 的左子树中所有左叶子之和，并将结果加到答案变量 $a n s$ 中。

最后返回答案即可。

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

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

方法二：栈 · Go 实现

思考

方法一的判定规则不变，只是把递归改成显式栈：弹出节点后，左叶子直接累加，否则将左孩子入栈；右孩子存在则入栈。

渐近复杂度相同，实现上去掉递归深度限制。

我们也可以将方法一的递归改为迭代，使用栈来模拟递归的过程。

与方法一类似，我们首先判断 root 是否为空，如果为空则返回 $0$ 。

否则，我们初始化答案变量 $a n s$ 为 $0$ ，然后初始化栈 $s t k$ ，将 root 加入栈中。

当栈不为空时，我们弹出栈顶元素 root，如果 root 的左子节点存在，我们判断其是否为叶子节点，如果是叶子节点，则将其值加到答案变量 $a n s$ 中，否则我们将其左子节点加入栈中。然后我们判断 root 的右子节点是否存在，如果存在，我们将其加入栈中。

最后返回答案即可。

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

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sumOfLeftLeaves(root *TreeNode) (ans int) {
	if root == nil {
		return 0
	}
	stk := []*TreeNode{root}
	for len(stk) > 0 {
		root = stk[len(stk)-1]
		stk = stk[:len(stk)-1]
		if root.Left != nil {
			if root.Left.Left == root.Left.Right {
				ans += root.Left.Val
			} else {
				stk = append(stk, root.Left)
			}
		}
		if root.Right != nil {
			stk = append(stk, root.Right)
		}
	}
	return
}

力扣原题 · Doocs 题解来源

426. 将二叉搜索树转化为排序的双向链表 🔒

中等1 种解法

标签：栈、树、深度优先搜索、二叉搜索树、链表、二叉树、双向链表

题目、示例与约束

将一个 二叉搜索树 就地转化为一个 已排序的双向循环链表 。

对于双向循环列表，你可以将左右孩子指针作为双向循环链表的前驱和后继指针，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。

特别地，我们希望可以原地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中最小元素的指针。

示例 1：

输入：root = [4,2,5,1,3] 


输出：[1,2,3,4,5]

解释：下图显示了转化后的二叉搜索树，实线表示后继关系，虚线表示前驱关系。

示例 2：

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

提示：

树中节点的数量在范围 [0, 2000] 中
-1000 <= Node.val <= 1000
树中的所有值都是 独一无二 的

方法一 · Go 实现

思考

BST 的中序遍历即为升序。若先收集节点再连边，需要额外数组。题目要求原地，用 $left / right$ 充当前驱后继。

中序遍历时把 $prev$ 与当前节点互指，并记下第一个节点为 $head$ ；遍历结束后再把 $head$ 与最后一个节点连成环。

先左后根再右，保证链接顺序与有序序列一致；哑元或空 $prev$ 用来识别链表头。

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Left *Node
 *     Right *Node
 * }
 */

func treeToDoublyList(root *Node) *Node {
	if root == nil {
		return root
	}
	var prev, head *Node

	var dfs func(root *Node)
	dfs = func(root *Node) {
		if root == nil {
			return
		}
		dfs(root.Left)
		if prev != nil {
			prev.Right = root
			root.Left = prev
		} else {
			head = root
		}
		prev = root
		dfs(root.Right)
	}
	dfs(root)
	prev.Right = head
	head.Left = prev
	return head
}

力扣原题 · Doocs 题解来源

427. 建立四叉树

中等1 种解法

标签：树、数组、分治、矩阵

题目、示例与约束

给你一个 n * n 矩阵 grid ，矩阵由若干 0 和 1 组成。请你用四叉树表示该矩阵 grid 。

你需要返回能表示矩阵 grid 的四叉树的根结点。

四叉树数据结构中，每个内部节点只有四个子节点。此外，每个节点都有两个属性：

val：储存叶子结点所代表的区域的值。1 对应 True，0 对应 False。注意，当 isLeaf 为 False 时，你可以把 True 或者 False 赋值给节点，两种值都会被判题机制接受。
isLeaf: 当这个节点是一个叶子结点时为 True，如果它有 4 个子节点则为 False 。

class Node {
    public boolean val;
    public boolean isLeaf;
    public Node topLeft;
    public Node topRight;
    public Node bottomLeft;
    public Node bottomRight;
}

我们可以按以下步骤为二维区域构建四叉树：

如果当前网格的值相同（即，全为 0 或者全为 1），将 isLeaf 设为 True ，将 val 设为网格相应的值，并将四个子节点都设为 Null 然后停止。
如果当前网格的值不同，将 isLeaf 设为 False，将 val 设为任意值，然后如下图所示，将当前网格划分为四个子网格。
使用适当的子网格递归每个子节点。

如果你想了解更多关于四叉树的内容，可以参考百科。

四叉树格式：

你不需要阅读本节来解决这个问题。只有当你想了解输出格式时才会这样做。输出为使用层序遍历后四叉树的序列化形式，其中 null 表示路径终止符，其下面不存在节点。

它与二叉树的序列化非常相似。唯一的区别是节点以列表形式表示 [isLeaf, val] 。

如果 isLeaf 或者 val 的值为 True ，则表示它在列表 [isLeaf, val] 中的值为 1 ；如果 isLeaf 或者 val 的值为 False ，则表示值为 0 。

示例 1：

输入：grid = [[0,1],[1,0]]
输出：[[0,1],[1,0],[1,1],[1,1],[1,0]]
解释：此示例的解释如下：
请注意，在下面四叉树的图示中，0 表示 false，1 表示 True 。

示例 2：

输入：grid = [[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,1],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0]]
输出：[[0,1],[1,1],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]]
解释：网格中的所有值都不相同。我们将网格划分为四个子网格。
topLeft，bottomLeft 和 bottomRight 均具有相同的值。
topRight 具有不同的值，因此我们将其再分为 4 个子网格，这样每个子网格都具有相同的值。
解释如下图所示：

提示：

n == grid.length == grid[i].length
n == 2^x 其中 0 <= x <= 6

方法一：DFS · Go 实现

思考

四叉树要求一块区域全同则为叶子，否则四等分。若对每个可能的子矩形都重新扫描，存在重复，但 $n \leq 64$ 且每次四分，总扫描量可接受。

DFS 扫描当前矩形是否同时出现 $0$ 与 $1$ ：若只有一种值则建叶子，否则递归四块并挂到四个孩子。

叶节点的 $val$ 取该块颜色；先判定全同再决定是否分裂，避免对纯色块继续切分。

DFS 递归遍历 grid，先判断 grid 是否为叶子节点，是则返回叶子节点相关信息；否则递归 grid 4 个子节点。

/**
 * Definition for a QuadTree node.
 * type Node struct {
 *     Val bool
 *     IsLeaf bool
 *     TopLeft *Node
 *     TopRight *Node
 *     BottomLeft *Node
 *     BottomRight *Node
 * }
 */

func construct(grid [][]int) *Node {
	var dfs func(a, b, c, d int) *Node
	dfs = func(a, b, c, d int) *Node {
		zero, one := 0, 0
		for i := a; i <= c; i++ {
			for j := b; j <= d; j++ {
				if grid[i][j] == 0 {
					zero = 1
				} else {
					one = 1
				}
			}
		}
		isLeaf := zero+one == 1
		val := isLeaf && one == 1
		node := &Node{Val: val, IsLeaf: isLeaf}
		if isLeaf {
			return node
		}
		node.TopLeft = dfs(a, b, (a+c)/2, (b+d)/2)
		node.TopRight = dfs(a, (b+d)/2+1, (a+c)/2, d)
		node.BottomLeft = dfs((a+c)/2+1, b, c, (b+d)/2)
		node.BottomRight = dfs((a+c)/2+1, (b+d)/2+1, c, d)
		return node
	}
	return dfs(0, 0, len(grid)-1, len(grid[0])-1)
}

力扣原题 · Doocs 题解来源

428. 序列化和反序列化 N 叉树 🔒

困难1 种解法

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

题目、示例与约束

序列化是指将一个数据结构转化为位序列的过程，因此可以将其存储在文件中或内存缓冲区中，以便稍后在相同或不同的计算机环境中恢复结构。

设计一个序列化和反序列化 N 叉树的算法。一个 N 叉树是指每个节点都有不超过 N 个孩子节点的有根树。序列化 / 反序列化算法的算法实现没有限制。你只需要保证 N 叉树可以被序列化为一个字符串并且该字符串可以被反序列化成原树结构即可。

例如，你需要序列化下面的 3-叉 树。

为 [1 [3[5 6] 2 4]]。你不需要以这种形式完成，你可以自己创造和实现不同的方法。

或者，您可以遵循 LeetCode 的层序遍历序列化格式，其中每组孩子节点由空值分隔。

例如，上面的树可以序列化为 [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]

你不一定要遵循以上建议的格式，有很多不同的格式，所以请发挥创造力，想出不同的方法来完成本题。

示例 1:

输入: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出: [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]

示例 2:

输入: root = [1,null,3,2,4,null,5,6]
输出: [1,null,3,2,4,null,5,6]

示例 3:

输入: root = []
输出: []

提示：

树中节点数目的范围是 [0, 10⁴].
0 <= Node.val <= 10⁴
N 叉树的高度小于等于 1000
不要使用类成员 / 全局变量 / 静态变量来存储状态。你的序列化和反序列化算法应是无状态的。

方法一：层序遍历 · Go 实现

思考

N 叉树孩子个数不定，前序若只写值无法知道一棵子树在何处结束。需要在每个节点的孩子列表后加入结束标记。

层序遍历：写出根值，弹出节点时依次写出孩子并入队，再写 $#$ 。反序列化按同一顺序：队列中的节点不断领取后续值作为孩子，直到遇到 $#$ 。

结束符与出队顺序一一对应，保证多叉列表可以还原，且空树写成空串。

我们可以采用层序遍历对 N 叉树进行序列化。从根节点开始，将其值加入结果，再将根节点入队。每次弹出一个节点时，依次将其所有孩子的值加入结果并入队，然后加入特殊字符 # 表示该节点的孩子列表结束。最后用逗号拼接成字符串返回。

反序列化时，将序列化字符串按分隔符切分。先根据第一个值创建根节点并入队，然后对队列中的每个节点，不断取出后续元素作为孩子，直到遇到 #。

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

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Children []*Node
 * }
 */

type Codec struct {
}

func Constructor() *Codec {
	return &Codec{}
}

func (this *Codec) serialize(root *Node) string {
	if root == nil {
		return ""
	}
	ans := []string{strconv.Itoa(root.Val)}
	q := []*Node{root}
	for len(q) > 0 {
		node := q[0]
		q = q[1:]
		for _, child := range node.Children {
			ans = append(ans, strconv.Itoa(child.Val))
			q = append(q, child)
		}
		ans = append(ans, "#")
	}
	return strings.Join(ans, ",")
}

func (this *Codec) deserialize(data string) *Node {
	if data == "" {
		return nil
	}
	vals := strings.Split(data, ",")
	v, _ := strconv.Atoi(vals[0])
	root := &Node{Val: v}
	q := []*Node{root}
	i := 1
	for len(q) > 0 {
		node := q[0]
		q = q[1:]
		for i < len(vals) && vals[i] != "#" {
			v, _ = strconv.Atoi(vals[i])
			child := &Node{Val: v}
			node.Children = append(node.Children, child)
			q = append(q, child)
			i++
		}
		i++
	}
	return root
}

/**
 * Your Codec object will be instantiated and called as such:
 * obj := Constructor();
 * data := obj.serialize(root);
 * ans := obj.deserialize(data);
 */

力扣原题 · Doocs 题解来源

429. N 叉树的层序遍历

中等2 种解法

标签：树、广度优先搜索

题目、示例与约束

给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。

树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。

示例 1：

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

示例 2：

输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出：[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]

提示：

树的高度不会超过 1000
树的节点总数在 [0, 10⁴] 之间

方法一：BFS · Go 实现

思考

层序结果按层分组。深度优先若不分层，会把不同层的值混在一起。

队列记录当前层：每次先记下队长，弹出这些节点写入本层列表，并把它们的孩子入队。空根返回空列表。

用队长界定一层，保证同一层从左到右，且孩子在下一轮才被处理。

我们首先判断根节点是否为空，若为空则直接返回空列表。

否则，我们创建一个队列 $q$ ，初始时将根节点加入队列。

当队列不为空时，我们循环以下操作：

创建一个空列表 $t$ ，用于存放当前层的节点值。
对于队列中的每个节点，将其值加入 $t$ 中，并将其子节点加入队列。
将 $t$ 加入结果列表 $a n s$ 。

最后返回结果列表 $a n s$ 。

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

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Children []*Node
 * }
 */

func levelOrder(root *Node) (ans [][]int) {
	if root == nil {
		return
	}
	q := []*Node{root}
	for len(q) > 0 {
		var t []int
		for n := len(q); n > 0; n-- {
			root = q[0]
			q = q[1:]
			t = append(t, root.Val)
			for _, child := range root.Children {
				q = append(q, child)
			}
		}
		ans = append(ans, t)
	}
	return
}

方法二：DFS · Go 实现

思考

方法一依赖队列。若按深度递归，把节点值追加到 $ans [i]$ ，层数不足时先扩一层，同样能得到层序。

少一个队列，递归栈承担层信息；同一层仍按孩子从左到右的访问顺序写入。

我们可以使用深度优先搜索的方法，遍历整棵树。

我们定义一个辅助函数 $d f s (r o o t, i)$ ，其中 $r o o t$ 表示当前节点，而 $i$ 表示当前层数。

在 $d f s$ 函数中，我们首先判断 $r o o t$ 是否为空，若为空则直接返回。

否则，我们判断 $a n s$ 的长度是否小于等于 $i$ ，若是则说明当前层还没有加入到 $a n s$ 中，我们需要先加入一个空列表。然后将 $r o o t$ 的值加入 $a n s [i]$ 中。

接着，我们遍历 $r o o t$ 的所有子节点，对于每个子节点，我们调用 $d f s (c h i l d, i + 1)$ 。

在主函数中，我们调用 $d f s (r o o t, 0)$ ，并返回 $a n s$ 。

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

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Children []*Node
 * }
 */

func levelOrder(root *Node) (ans [][]int) {
	var dfs func(root *Node, i int)
	dfs = func(root *Node, i int) {
		if root == nil {
			return
		}
		if len(ans) <= i {
			ans = append(ans, []int{})
		}
		ans[i] = append(ans[i], root.Val)
		for _, child := range root.Children {
			dfs(child, i+1)
		}
	}
	dfs(root, 0)
	return
}

力扣原题 · Doocs 题解来源

437. 路径总和 III

中等1 种解法

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

题目、示例与约束

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的路径的数目。

路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

示例 1：

输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示。

示例 2：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：3

提示:

二叉树的节点个数的范围是 [0,1000]
-10⁹ <= Node.val <= 10⁹
-1000 <= targetSum <= 1000

方法一：哈希表 + 前缀和 + 递归 · Go 实现

思考

路径必须向下，枚举每个祖先再向下扫描是 $O (n^{2})$ 。路径和等于 $targetSum$ 可改写成「当前前缀和减去某个祖先前缀和」。

先序累加前缀和 $s$ ，用哈希表统计根到当前结点的前缀出现次数， $cnt [s - targetSum]$ 即以此为终点的合法路径数。回溯时撤销 $s$ ，避免把另一条分支算进来。

初始 $cnt [0] = 1$ ，对应从根出发整段刚好等于目标。先查询再插入，路径不含「当前结点用两次」。

我们可以运用前缀和的思想，对二叉树进行递归遍历，同时用哈希表 $cnt$ 统计从根节点到当前节点的路径上各个前缀和出现的次数。

我们设计一个递归函数 $dfs(node, s)$ ，表示当前遍历到的节点为 $node$ ，从根节点到当前节点的路径上的前缀和为 $s$ 。函数的返回值是统计以 $node$ 节点及其子树节点作为路径终点且路径和为 $targetSum$ 的路径数目。那么答案就是 $dfs(root, 0)$ 。

函数 $dfs(node, s)$ 的递归过程如下：

如果当前节点 $node$ 为空，则返回 $0$ 。
计算从根节点到当前节点的路径上的前缀和 $s$ 。
用 $cnt [s - targetSum]$ 表示以当前节点为路径终点且路径和为 $targetSum$ 的路径数目，其中 $cnt [s - targetSum]$ 即为 $cnt$ 中前缀和为 $s - targetSum$ 的个数。
将前缀和 $s$ 的计数值加 $1$ ，即 $cnt [s] = cnt [s] + 1$ 。
递归地遍历当前节点的左右子节点，即调用函数 $dfs(node.left, s)$ 和 $dfs(node.right, s)$ ，并将它们的返回值相加。
在返回值计算完成以后，需要将当前节点的前缀和 $s$ 的计数值减 $1$ ，即执行 $cnt [s] = cnt [s] - 1$ 。
最后返回答案。

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

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func pathSum(root *TreeNode, targetSum int) int {
	cnt := map[int]int{0: 1}
	var dfs func(*TreeNode, int) int
	dfs = func(node *TreeNode, s int) int {
		if node == nil {
			return 0
		}
		s += node.Val
		ans := cnt[s-targetSum]
		cnt[s]++
		ans += dfs(node.Left, s) + dfs(node.Right, s)
		cnt[s]--
		return ans
	}
	return dfs(root, 0)
}

力扣原题 · Doocs 题解来源

450. 删除二叉搜索树中的节点

中等1 种解法

标签：树、二叉搜索树、二叉树

题目、示例与约束

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：

首先找到需要删除的节点；
如果找到了，删除它。

示例 1:

输入：root = [5,3,6,2,4,null,7], key = 3
输出：[5,4,6,2,null,null,7]
解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
另一个正确答案是 [5,2,6,null,4,null,7]。

示例 2:

输入: root = [5,3,6,2,4,null,7], key = 0
输出: [5,3,6,2,4,null,7]
解释: 二叉树不包含值为 0 的节点

示例 3:

输入: root = [], key = 0
输出: []

提示:

节点数的范围 [0, 10⁴].
-10⁵ <= Node.val <= 10⁵
节点值唯一
root 是合法的二叉搜索树
-10⁵ <= key <= 10⁵

进阶： 要求算法时间复杂度为 O(h)，h 为树的高度。

方法一：递归 · Go 实现

思考

BST 删除要保持中序有序。找到目标后，若只有一侧孩子则提升该孩子；两侧都在时，需选一个后继或前驱顶替。

按大小关系递归进入左或右。命中后：无左返右、无右返左；否则把整棵左子树挂到右子树最左结点的左侧，再返回右子树。

右子树的最左结点是中序后继，其左孩子为空，挂上原左子树后中序仍然有序，且只需一次下行。

二叉搜索树有以下性质：

若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
任意节点的左、右子树也分别为二叉搜索树。

我们可以递归判断当前节点 $r o o t$ 与 $k e y$ 的大小关系：

若 $r o o t . v a l > k e y$ ，则递归左子树；
若 $r o o t . v a l < k e y$ ，则递归右子树；
若 $r o o t . v a l = k e y$ ，则进一步判断：
1. 若 $r o o t$ 没有左子树，则 $r o o t . r i g h t$ 顶替 $r o o t$ 的位置；
2. 若 $r o o t$ 没有右子树，则 $r o o t . l e f t$ 顶替 $r o o t$ 的位置；
3. 若 $r o o t$ 同时存在左右子树，则将左子树转移至右子树的最左节点的左子树上，然后 $r o o t . r i g h t$ 顶替 $r o o t$ 的位置。

时间复杂度 $O (H)$ ，其中 $H$ 是树的高度。

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

力扣原题 · Doocs 题解来源

501. 二叉搜索树中的众数

简单2 种解法

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

题目、示例与约束

给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有众数（即，出现频率最高的元素）。

如果树中有不止一个众数，可以按 任意顺序 返回。

假定 BST 满足如下定义：

结点左子树中所含节点的值 小于等于 当前节点的值
结点右子树中所含节点的值 大于等于 当前节点的值
左子树和右子树都是二叉搜索树

示例 1：

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

示例 2：

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

提示：

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

进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）

方法一 · Go 实现

思考

众数即出现次数最多的值。若先遍历整棵树再哈希计数，时间和空间均为 $O (n)$ ，在 $n \leq 10^{4}$ 时可以接受，但没有用到二叉搜索树的有序性。

中序遍历得到的是非降序列，相同值必然相邻。因此只需在中序过程中维护前驱、当前连续次数与历史最大次数：次数更大则重置答案，次数持平则追加。一遍中序即可在 $O (h)$ 额外空间内收集全部众数。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func findMode(root *TreeNode) []int {
	mx, cnt := 0, 0
	var prev *TreeNode
	var ans []int
	var dfs func(root *TreeNode)
	dfs = func(root *TreeNode) {
		if root == nil {
			return
		}
		dfs(root.Left)
		if prev != nil && prev.Val == root.Val {
			cnt++
		} else {
			cnt = 1
		}
		if cnt > mx {
			ans = []int{root.Val}
			mx = cnt
		} else if cnt == mx {
			ans = append(ans, root.Val)
		}
		prev = root
		dfs(root.Right)
	}
	dfs(root)
	return ans
}

方法二：显式栈中序遍历 · Go 实现

思考

众数是出现次数最多的值。先遍历整棵树再哈希计数，在 $n \leq 10^{4}$ 时时间够用，但没有用到二叉搜索树的有序性。

中序会先走进左孩子。一条长度为 $10^{4}$ 的链按结点个数递归，调用栈会溢出。

中序得到的是非降序列，相同值必然相邻。因此只需要前一个值、当前连续次数和历史最大次数，不必等子树返回。

用显式栈做中序遍历。进入结点时压入退出标记和左孩子；退出时按连续次数更新答案，再压入右孩子。次数更大就重置答案，次数持平就追加。

二叉搜索树的中序遍历是非降序列，相同的值必然相邻。我们用显式栈完成这次中序遍历，并维护前一个值、当前连续次数和历史最大次数。进入结点时压入退出标记和左孩子；退出时，若当前值与前一个值相同则连续次数加一，否则置为 $1$ 。连续次数超过历史最大次数时重置答案，相等时把当前值追加进答案，然后压入右孩子。

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

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func findMode(root *TreeNode) []int {
	mx, cnt, prev := 0, 0, 0
	has := false
	var ans []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, state := cur.node, cur.state
		if node == nil {
			continue
		}
		if state == 0 {
			stk = append(stk, frame{node, 1}, frame{node.Left, 0})
			continue
		}
		if has && prev == node.Val {
			cnt++
		} else {
			cnt = 1
		}
		if cnt > mx {
			ans = []int{node.Val}
			mx = cnt
		} else if cnt == mx {
			ans = append(ans, node.Val)
		}
		prev = node.Val
		has = true
		stk = append(stk, frame{node.Right, 0})
	}
	return ans
}

力扣原题 · Doocs 题解来源

508. 出现次数最多的子树元素和

中等2 种解法

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

题目、示例与约束

给你一个二叉树的根结点 root ，请返回出现次数最多的子树元素和。如果有多个元素出现的次数相同，返回所有出现次数最多的子树元素和（不限顺序）。

一个结点的 「子树元素和」 定义为以该结点为根的二叉树上所有结点的元素之和（包括结点本身）。

示例 1：

输入: root = [5,2,-3]
输出: [2,-3,4]

示例 2：

输入: root = [5,2,-5]
输出: [2]

提示:

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

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

思考

子树和 = 左子树和 + 右子树和 + 根值，必须先得到两棵子树的和。若对每个节点再扫一遍子树，会重复累加。

后序 DFS 在回溯时算出当前子树和，并用哈希表统计每个和出现的次数。全部节点处理完后，取出现次数最大的那些和。一次遍历同时完成求和与计数。

我们可以使用一个哈希表 $cnt$ 记录每个子树元素和出现的次数，然后使用深度优先搜索遍历整棵树，统计每个子树的元素和，并更新 $cnt$ 。

最后，我们遍历 $cnt$ ，找到所有出现次数最多的子树元素和。

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

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func findFrequentTreeSum(root *TreeNode) (ans []int) {
	cnt := map[int]int{}
	var mx int
	var dfs func(*TreeNode) int
	dfs = func(root *TreeNode) int {
		if root == nil {
			return 0
		}
		s := root.Val + dfs(root.Left) + dfs(root.Right)
		cnt[s]++
		mx = max(mx, cnt[s])
		return s
	}
	dfs(root)
	for k, v := range cnt {
		if v == mx {
			ans = append(ans, k)
		}
	}
	return
}

方法二：哈希表 + 显式栈 · Go 实现

思考

子树和等于左子树和、右子树和与根值之和，必须先得到两棵子树的和。若对每个结点再扫一遍子树，会重复累加。后序递归在回溯时计算当前和，在较短的树上是对的。

结点个数可达 $10^{4}$ 。左链使这次后序按结点个数递归，调用栈会溢出。

每个结点的和只由左右子树的和决定，所以必须先处理孩子，再处理父亲。出现次数可以边走边记在哈希表里。

因此用显式栈做后序遍历。进入结点时压入退出标记和左右孩子；退出时用左右子树和算出当前和，写入哈希表。全部结点处理完后，取出出现次数最大的那些和。

我们用哈希表 $cnt$ 记录每个子树元素和出现的次数，并用显式栈对二叉树做后序遍历。进入结点时压入退出标记，再压入右孩子和左孩子；退出时，左右子树的和已经记下，当前子树和为二者与结点值之和，并更新 $cnt$ 。

最后遍历 $cnt$ ，找到所有出现次数最多的子树元素和。

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

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func findFrequentTreeSum(root *TreeNode) (ans []int) {
	cnt := map[int]int{}
	sub := map[*TreeNode]int{}
	mx := 0
	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, state := cur.node, cur.state
		if node == nil {
			continue
		}
		if 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, r := 0, 0
		if node.Left != nil {
			l = sub[node.Left]
		}
		if node.Right != nil {
			r = sub[node.Right]
		}
		s := node.Val + l + r
		cnt[s]++
		mx = max(mx, cnt[s])
		sub[node] = s
	}
	for k, v := range cnt {
		if v == mx {
			ans = append(ans, k)
		}
	}
	return
}

力扣原题 · Doocs 题解来源

510. 二叉搜索树中的中序后继 II 🔒

中等1 种解法

标签：树、二叉搜索树、二叉树

题目、示例与约束

给定一棵二叉搜索树和其中的一个节点 node ，找到该节点在树中的中序后继。如果节点没有中序后继，请返回 null 。

一个节点 node 的中序后继是键值比 node.val 大所有的节点中键值最小的那个。

你可以直接访问结点，但无法直接访问树。每个节点都会有其父节点的引用。节点 Node 定义如下：

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node parent;
}

示例 1：

输入：tree = [2,1,3], node = 1
输出：2
解析：1 的中序后继结点是 2 。注意节点和返回值都是 Node 类型的。

示例 2：

输入：tree = [5,3,6,2,4,null,null,1], node = 6
输出：null
解析：该结点没有中序后继，因此返回 null 。

提示：

树中节点的数目在范围 [1, 10⁴] 内。
-10⁵ <= Node.val <= 10⁵
树中各结点的值均保证唯一。

进阶：你能否在不访问任何结点的值的情况下解决问题?

方法一：分情况讨论 · Go 实现

思考

普通 BST 中序后继可中序遍历或从根下行，但本题只有父指针、没有整棵树入口，不能从根重走。

后继只有两类：存在右子树时，是右子树最左节点；否则沿父指针上爬，直到当前节点是其父的左孩子，父节点即为后继。两种情况都沿一条链走，无需额外存储。

如果 $node$ 有右子树，那么 $node$ 的中序后继节点是右子树中最左边的节点。

如果 $node$ 没有右子树，那么如果 $node$ 是其父节点的右子树，我们就一直向上搜索，直到节点的父节点为空，或者节点是其父节点的左子树，此时父节点就是中序后继节点。

时间复杂度 $O (h)$ ，其中 $h$ 是二叉树的高度。空间复杂度 $O (1)$ 。

/**
 * Definition for Node.
 * type Node struct {
 *     Val int
 *     Left *Node
 *     Right *Node
 *     Parent *Node
 * }
 */

func inorderSuccessor(node *Node) *Node {
	if node.Right != nil {
		node = node.Right
		for node.Left != nil {
			node = node.Left
		}
		return node
	}
	for node.Parent != nil && node == node.Parent.Right {
		node = node.Parent
	}
	return node.Parent
}

力扣原题 · Doocs 题解来源

513. 找树左下角的值

中等2 种解法

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

题目、示例与约束

给定一个二叉树的 根节点 root。

请找出该二叉树的 最底层最左边 节点的值。

示例 1:

输入：root = [2,1,3]
输出：1
解释：最后一行是 [1, 3]，因此最左边的值是 1。

示例 2:

输入：[1,2,3,4,null,5,6,null,null,7]
输出：7
解释：最后一层只有节点 7。

提示:

二叉树的节点个数的范围是 [1, 10⁴]
-2³¹ <= Node.val <= 2³¹ - 1

方法一：BFS · Go 实现

思考

最底层最左侧的值，等于层序遍历最后一层的第一个节点。逐层 BFS 时，队列头部就是当前层最左节点。

每层开始时记下队首值，并展开左右孩子。循环结束时记下的便是最后一层最左值。层序保证深度最大的一层最后被处理。

BFS 找最后一层第一个节点。

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

方法二：DFS · Go 实现

思考

BFS 需要 $O (w)$ 队列。若改为 DFS，只需沿树高记录「首次达到的更大深度」。

先左后右的先序会先碰到每一层最左节点；仅当深度刷新最大值时更新答案。额外空间降为递归栈，结果与层序一致。

DFS 先序遍历，找深度最大的，且第一次被遍历到的节点。

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

力扣原题 · Doocs 题解来源

515. 在每个树行中找最大值

中等2 种解法

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

题目、示例与约束

给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。

示例1：

输入: root = [1,3,2,5,3,null,9]
输出: [1,3,9]

示例2：

输入: root = [1,2,3]
输出: [1,3]

提示：

二叉树的节点个数的范围是 [0,10⁴]
-2³¹ <= Node.val <= 2³¹ - 1

方法一：BFS · Go 实现

思考

每一层的最大值可在层序遍历时当场求出。将根入队，按层弹出，维护本层最大值并加入孩子。

一层处理完就得到一个答案。空树直接返回空列表。时间与节点数成正比。

我们定义一个队列 $q$ ，将根节点放入队列中。每次从队列中取出当前层的所有节点，找出最大值，然后将下一层的所有节点放入队列中，直到队列为空。

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

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

方法二：DFS · Go 实现

思考

BFS 按层很自然，但需要队列。DFS 只要带着深度往下走：深度等于答案长度时追加，否则与已有值取最大。

先序保证每一层第一次到达时创建槽位。额外空间是递归深度，结果与层序相同。

DFS 先序遍历，找每个深度最大的节点值。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func largestValues(root *TreeNode) []int {
	var ans []int
	var dfs func(*TreeNode, int)
	dfs = func(root *TreeNode, curr int) {
		if root == nil {
			return
		}
		if curr == len(ans) {
			ans = append(ans, root.Val)
		} else {
			ans[curr] = max(ans[curr], root.Val)
		}
		dfs(root.Left, curr+1)
		dfs(root.Right, curr+1)
	}
	dfs(root, 0)
	return ans
}

力扣原题 · Doocs 题解来源

530. 二叉搜索树的最小绝对差

简单2 种解法

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

题目、示例与约束

给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。

差值是一个正数，其数值等于两值之差的绝对值。

示例 1：

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

示例 2：

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

提示：

树中节点的数目范围是 [2, 10⁴]
0 <= Node.val <= 10⁵

注意：本题与 783 https://leetcode.cn/problems/minimum-distance-between-bst-nodes/ 相同

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

思考

任意两点差的最小值，在无序树上要比较所有点对。BST 的中序是递增序列，最小差只可能出现在相邻两项之间。

中序遍历时维护前驱，用当前值减前驱更新答案。前驱初值取负无穷，避免第一个节点参与减法。一次中序即可。

题目需要我们求任意两个节点值之间的最小差值，而二叉搜索树的中序遍历是一个递增序列，因此我们只需要求中序遍历中相邻两个节点值之间的最小差值即可。

我们可以使用递归的方法来实现中序遍历，过程中用一个变量 $pre$ 来保存前一个节点的值，这样我们就可以在遍历的过程中求出相邻两个节点值之间的最小差值。

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

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func getMinimumDifference(root *TreeNode) int {
	const inf int = 1 << 30
	ans, pre := inf, -inf
	var dfs func(*TreeNode)
	dfs = func(root *TreeNode) {
		if root == nil {
			return
		}
		dfs(root.Left)
		ans = min(ans, root.Val-pre)
		pre = root.Val
		dfs(root.Right)
	}
	dfs(root)
	return ans
}

方法二：显式栈中序遍历 · Go 实现

思考

任意两点差的最小值，在无序树上要比较所有点对。二叉搜索树的中序是递增序列，最小差只可能出现在相邻两项之间。先递归中序、用当前值减去前驱，在较短的树上是对的。

结点个数可达 $10^{4}$ 。左链使这次中序按结点个数递归，调用栈会溢出。

每个结点只需要前一个值，不需要子树的返回值，只要先走完左子树、再看自己、再走右子树。

因此用显式栈做中序遍历。进入结点时压入退出标记和左孩子；退出时用当前值减去前驱更新答案，再压入右孩子。前驱初值取负无穷，第一个结点不会成为答案。

题目要求任意两个结点值的最小差。二叉搜索树的中序遍历是递增序列，所以最小差只会出现在中序相邻的两个值之间。

我们用显式栈完成这次中序遍历，并用 $pre$ 保存前一个结点的值，初值为负无穷。进入结点时压入退出标记和左孩子；退出时用当前值减去 $pre$ 更新答案，然后把 $pre$ 改成当前值，再压入右孩子。

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

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func getMinimumDifference(root *TreeNode) int {
	const inf int = 1 << 30
	ans, pre := inf, -inf
	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, state := cur.node, cur.state
		if node == nil {
			continue
		}
		if state == 0 {
			stk = append(stk, frame{node, 1}, frame{node.Left, 0})
			continue
		}
		ans = min(ans, node.Val-pre)
		pre = node.Val
		stk = append(stk, frame{node.Right, 0})
	}
	return ans
}

力扣原题 · Doocs 题解来源

536. 从字符串生成二叉树 🔒

中等1 种解法

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

题目、示例与约束

你需要用一个包括括号和整数的字符串构建一棵二叉树。

输入的字符串代表一棵二叉树。它包括整数和随后的 0 、1 或 2 对括号。整数代表根的值，一对括号内表示同样结构的子树。

若存在子结点，则从左子结点开始构建。

示例 1:

输入： s = "4(2(3)(1))(6(5))"
输出： [4,2,6,3,1,5]

示例 2:

输入： s = "4(2(3)(1))(6(5)(7))"
输出： [4,2,6,3,1,5,7]

示例 3:

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

提示：

0 <= s.length <= 3 * 10⁴
输入字符串中只包含 '(', ')', '-' 和 '0' ~ '9'
树中所有数字的值最多不超过 2³⁰。

方法一 · Go 实现

思考

串由「整数值 + 可选的左子树括号 + 可选的右子树括号」递归构成。线性扫描要同时切出数值和配对的括号段。

找不到 '(' 则整段是叶子。否则数值在首个括号之前；再用计数匹配括号，第一次配平的是左子树，其后配平的是右子树，分别递归。括号深度保证切分与嵌套结构一致。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func str2tree(s string) *TreeNode {
	var dfs func(s string) *TreeNode
	dfs = func(s string) *TreeNode {
		if s == "" {
			return nil
		}
		p := strings.IndexAny(s, "(")
		if p == -1 {
			v, _ := strconv.Atoi(s)
			return &TreeNode{Val: v}
		}
		v, _ := strconv.Atoi(s[:p])
		root := &TreeNode{Val: v}
		start := p
		cnt := 0
		for i := p; i < len(s); i++ {
			if s[i] == '(' {
				cnt++
			} else if s[i] == ')' {
				cnt--
			}
			if cnt == 0 {
				if p == start {
					root.Left = dfs(s[start+1 : i])
					start = i + 1
				} else {
					root.Right = dfs(s[start+1 : i])
				}
			}
		}
		return root
	}
	return dfs(s)
}

力扣原题 · Doocs 题解来源

538. 把二叉搜索树转换为累加树

中等3 种解法

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

题目、示例与约束

给出二叉搜索树的根节点 root，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），将其转换为一个更大的树，使得原始二叉搜索树中的每个节点值都变为原本值加上原本二叉搜索树中所有比该节点值大的节点值的总和。

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

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

注意：本题和 1038: https://leetcode.cn/problems/binary-search-tree-to-greater-sum-tree/ 相同

示例 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]

示例 3：

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

示例 4：

输入：root = [3,2,4,1]
输出：[7,9,4,10]

提示：

树中的节点数介于 0 和 10⁴之间。
每个节点的值介于 -10⁴ 和 10⁴ 之间。
树中的所有值 互不相同 。
给定的树为二叉搜索树。

方法一：递归 · Go 实现

思考

把每个节点改成「不小于它的所有值之和」。BST 中这些值正好是反中序（右-根-左）已经走过的节点。

反中序累加到 $s$ ，再写回当前节点。右子树先于左子树处理，保证用到的都是更大的键。一次遍历完成。

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

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

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func convertBST(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 (h)$ 栈。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 convertBST(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
}

方法三：显式栈 · Go 实现

思考

把每个结点改成不小于它的所有值之和。二叉搜索树里这些值正好是反中序（右、根、左）已经走过的结点。先递归走右子树再写回，在较短的树上是对的。

结点个数可达 $10^{4}$ 。右链使这次遍历按结点个数递归，调用栈会溢出。

累加和只依赖已经访问过的更大的键，每个结点不需要子树的返回值，只要先处理右孩子、再改自己、再处理左孩子。

因此用显式栈做反中序。进入结点时压入退出标记和右孩子；退出时把当前值累加进 $s$ 并写回，再压入左孩子。

我们用显式栈按“右、根、左”的顺序遍历二叉搜索树。进入结点时压入退出标记和右孩子；退出时把结点值累加到 $s$ ，再把 $s$ 写回该结点，然后压入左孩子。

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

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func convertBST(root *TreeNode) *TreeNode {
	s := 0
	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, state := cur.node, cur.state
		if node == nil {
			continue
		}
		if state == 0 {
			stk = append(stk, frame{node, 1}, frame{node.Right, 0})
			continue
		}
		s += node.Val
		node.Val = s
		stk = append(stk, frame{node.Left, 0})
	}
	return root
}

力扣原题 · Doocs 题解来源

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

230. 二叉搜索树中第 K 小的元素 ​

235. 二叉搜索树的最近公共祖先 ​

236. 二叉树的最近公共祖先 ​

250. 统计同值子树 🔒 ​

255. 验证二叉搜索树的前序遍历序列 🔒 ​

257. 二叉树的所有路径 ​

270. 最接近的二叉搜索树值 🔒 ​

272. 最接近的二叉搜索树值 II 🔒 ​

285. 二叉搜索树中的中序后继 🔒 ​

298. 二叉树最长连续序列 🔒 ​

314. 二叉树的垂直遍历 🔒 ​

331. 验证二叉树的前序序列化 ​

333. 最大二叉搜索子树 🔒 ​

337. 打家劫舍 III ​

366. 寻找二叉树的叶子节点 🔒 ​

404. 左叶子之和 ​

426. 将二叉搜索树转化为排序的双向链表 🔒 ​

427. 建立四叉树 ​

428. 序列化和反序列化 N 叉树 🔒 ​

429. N 叉树的层序遍历 ​

437. 路径总和 III ​

450. 删除二叉搜索树中的节点 ​

501. 二叉搜索树中的众数 ​

508. 出现次数最多的子树元素和 ​

510. 二叉搜索树中的中序后继 II 🔒 ​

513. 找树左下角的值 ​

515. 在每个树行中找最大值 ​

530. 二叉搜索树的最小绝对差 ​

536. 从字符串生成二叉树 🔒 ​

538. 把二叉搜索树转换为累加树 ​

继续阅读

LeetCode Go · 树与二叉树（2）

230. 二叉搜索树中第 K 小的元素

235. 二叉搜索树的最近公共祖先

236. 二叉树的最近公共祖先

250. 统计同值子树 🔒

255. 验证二叉搜索树的前序遍历序列 🔒

257. 二叉树的所有路径

270. 最接近的二叉搜索树值 🔒

272. 最接近的二叉搜索树值 II 🔒

285. 二叉搜索树中的中序后继 🔒

298. 二叉树最长连续序列 🔒

314. 二叉树的垂直遍历 🔒

331. 验证二叉树的前序序列化

333. 最大二叉搜索子树 🔒

337. 打家劫舍 III

366. 寻找二叉树的叶子节点 🔒

404. 左叶子之和

426. 将二叉搜索树转化为排序的双向链表 🔒

427. 建立四叉树

428. 序列化和反序列化 N 叉树 🔒

429. N 叉树的层序遍历

437. 路径总和 III

450. 删除二叉搜索树中的节点

501. 二叉搜索树中的众数

508. 出现次数最多的子树元素和

510. 二叉搜索树中的中序后继 II 🔒

513. 找树左下角的值

515. 在每个树行中找最大值

530. 二叉搜索树的最小绝对差

536. 从字符串生成二叉树 🔒

538. 把二叉搜索树转换为累加树