LeetCode Go · 树与二叉树（1）

返回题库与筛选 · 收录范围与使用说明

来源与许可

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

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

94. 二叉树的中序遍历

简单3 种解法

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

题目、示例与约束

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

 

示例 1：

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

示例 2：

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

示例 3：

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

 

提示：

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

 

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

方法一：递归遍历 · Go 实现

思考

中序遍历的顺序是「左、根、右」。树本身按递归定义，因此可以直接递归：先走完左子树，再记录根，再走右子树。 $n\le 100$，最坏 $O(n)$ 的递归栈可以接受。进阶才要求改成迭代。

我们先递归左子树，再访问根节点，接着递归右子树。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 是二叉树的节点数，空间复杂度主要取决于递归调用的栈空间。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderTraversal(root *TreeNode) (ans []int) {
	var dfs func(*TreeNode)
	dfs = func(root *TreeNode) {
		if root == nil {
			return
		}
		dfs(root.Left)
		ans = append(ans, root.Val)
		dfs(root.Right)
	}
	dfs(root)
	return
}

方法二：栈实现非递归遍历 · Go 实现

思考

方法一已经得到正确序列，进阶要去掉系统递归。递归的本质是一路向左，走不动再弹出处理、转向右子树。用显式栈模拟这一过程：有左孩子就压栈下探，否则弹出访问并改走右孩子。顺序与中序相同，空间仍为 $O(n)$。

非递归的思路如下：

1. 定义一个栈 $stk$
2. 将树的左节点依次入栈
3. 左节点为空时，弹出栈顶元素并处理
4. 重复 2-3 的操作

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 是二叉树的节点数，空间复杂度主要取决于栈空间。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderTraversal(root *TreeNode) (ans []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]
			ans = append(ans, root.Val)
			root = root.Right
		}
	}
	return
}

方法三：Morris 实现中序遍历 · Go 实现

思考

方法二仍把空间留在 $O(h)$。若还要 $O(1)$ 额外空间，可以利用 Morris 的观察：左子树中最右结点的后继本来就是当前根，只是右指针空着。临时把这条空指针接到根上，沿左链走下去；回来时再拆掉。树自身的空指针充当栈，中序顺序不变，空间为 $O(1)$。

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

遍历二叉树节点，

1. 若当前节点 root 的左子树为空，将当前节点值添加至结果列表 ans 中，并将当前节点更新为 root.right
2. 若当前节点 root 的左子树不为空，找到左子树的最右节点 prev（也即是 root 节点在中序遍历下的前驱节点）：
   • 若前驱节点 prev 的右子树为空，将前驱节点的右子树指向当前节点 root，并将当前节点更新为 root.left。
   • 若前驱节点 prev 的右子树不为空，将当前节点值添加至结果列表 ans 中，然后将前驱节点右子树指向空（即解除 prev 与 root 的指向关系），并将当前节点更新为 root.right。
3. 循环以上步骤，直至二叉树节点为空，遍历结束。

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

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderTraversal(root *TreeNode) (ans []int) {
	for root != nil {
		if root.Left == nil {
			ans = append(ans, root.Val)
			root = root.Right
		} else {
			prev := root.Left
			for prev.Right != nil && prev.Right != root {
				prev = prev.Right
			}
			if prev.Right == nil {
				prev.Right = root
				root = root.Left
			} else {
				ans = append(ans, root.Val)
				prev.Right = nil
				root = root.Right
			}
		}
	}
	return
}

力扣原题 · Doocs 题解来源

95. 不同的二叉搜索树 II

中等1 种解法

标签：树、二叉搜索树、动态规划、回溯、二叉树

题目、示例与约束

给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。

 

示例 1：

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

示例 2：

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

 

提示：

• 1 <= n <= 8

方法一：DFS · Go 实现

思考

要枚举 $1..n$ 能构成的全部二叉搜索树。一旦选定根 $v$，左子树只能用 $[1,v-1]$，右子树只能用 $[v+1,n]$，左右彼此独立。因此可以按区间切分：枚举根，递归生成左右所有形态，再做笛卡尔积；空区间对应一棵空树。

$n\le 8$，卡特兰数不大，直接搜索即可。

我们设计一个函数 $dfs(i,j)$，返回由 $[i,j]$ 组成的所有可行的二叉搜索树，那么答案就是 $dfs(1,n)$。

函数 $dfs(i,j)$ 的执行步骤如下：

1. 如果 $i>j$，那么说明此时没有数字可以构成二叉搜索树，返回由一个空节点组成的列表。
2. 如果 $i\le j$，那么我们枚举 $[i,j]$ 中的数字 $v$ 作为根节点，那么根节点 $v$ 的左子树由 $[i,v-1]$ 组成，右子树由 $[v+1,j]$ 组成，最后将左右子树的所有组合笛卡尔积，即 $left\times right$，加上根节点 $v$，得到以 $v$ 为根节点的所有二叉搜索树。

时间复杂度 $O(n\times G(n))$，空间复杂度 $O(n\times G(n))$。其中 $G(n)$ 是卡特兰数。

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

力扣原题 · Doocs 题解来源

96. 不同的二叉搜索树

中等1 种解法

标签：树、二叉搜索树、数学、动态规划、二叉树

题目、示例与约束

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

 

示例 1：

输入：n = 3
输出：5

示例 2：

输入：n = 1
输出：1

 

提示：

• 1 <= n <= 19

方法一：动态规划 · Go 实现

思考

上一题要列出所有树，这一题只要个数。结构相同：选定根后，左右子树的形态数相乘，再对根求和。不同之处在于「树的形态」可以换成「节点个数」——任意 $i$ 个连续整数能构成的 BST 数量相同。

令 $f[i]$ 为 $i$ 个节点的方案数，空树 $f[0]=1$，按节点数从小到大递推，避免对同一规模重复搜索。

我们定义 $f[i]$ 表示 $[1,i]$ 能产生的二叉搜索树的个数，初始时 $f[0]=1$，答案为 $f[n]$。

我们可以枚举节点数 $i$，那么左子树节点数 $j\in [0,i-1]$，右子树节点数 $k=i-j-1$，左子树节点数和右子树节点数的组合数为 $f[j]\times f[k]$，因此 $f[i]=\sum _{j=0}^{i-1}f[j]\times f[i-j-1]$。

最后返回 $f[n]$ 即可。

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

func numTrees(n int) int {
	f := make([]int, n+1)
	f[0] = 1
	for i := 1; i <= n; i++ {
		for j := 0; j < i; j++ {
			f[i] += f[j] * f[i-j-1]
		}
	}
	return f[n]
}

力扣原题 · Doocs 题解来源

98. 验证二叉搜索树

中等1 种解法

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

题目、示例与约束

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

• 节点的左子树只包含 严格小于 当前节点的数。
• 节点的右子树只包含 严格大于 当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

 

示例 1：

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

示例 2：

输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

 

提示：

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

方法一：递归 · Go 实现

思考

仅检查「左孩子小于根、右孩子大于根」并不充分：左子树里的最大值也必须小于根。可以给每棵子树传入允许取值的区间，也可以利用 BST 的定义——中序序列必须严格递增。

中序时记下上一个值，当前值必须更大。递归左、比较、再递归右，一遍即可发现违规。空树合法。

我们可以对二叉树进行递归中序遍历，如果遍历到的结果是严格升序的，那么这棵树就是一个二叉搜索树。

因此，我们使用一个变量 $\mathit{\text{prev}}$ 来保存上一个遍历到的节点，初始时 $\mathit{\text{prev}}=-\mathrm{\infty }$，然后我们递归遍历左子树，如果左子树不是二叉搜索树，直接返回 $\mathit{\text{False}}$，否则判断当前节点的值是否大于 $\mathit{\text{prev}}$，如果不是，返回 $\mathit{\text{False}}$，否则更新 $\mathit{\text{prev}}$ 为当前节点的值，然后递归遍历右子树。

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

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isValidBST(root *TreeNode) bool {
	var prev *TreeNode
	var dfs func(*TreeNode) bool
	dfs = func(root *TreeNode) bool {
		if root == nil {
			return true
		}
		if !dfs(root.Left) {
			return false
		}
		if prev != nil && prev.Val >= root.Val {
			return false
		}
		prev = root
		return dfs(root.Right)
	}
	return dfs(root)
}

力扣原题 · Doocs 题解来源

99. 恢复二叉搜索树

中等1 种解法

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

题目、示例与约束

给你二叉搜索树的根节点 root ，该树中的 恰好 两个节点的值被错误地交换。请在不改变其结构的情况下，恢复这棵树 。

 

示例 1：

输入：root = [1,3,null,null,2]
输出：[3,1,null,null,2]
解释：3 不能是 1 的左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。

示例 2：

输入：root = [3,1,4,null,null,2]
输出：[2,1,4,null,null,3]
解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。

 

提示：

• 树上节点的数目在范围 [2, 1000] 内
• -231 <= Node.val <= 231 - 1

 

进阶：使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用 O(1) 空间的解决方案吗？

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

思考

二叉搜索树的中序序列应严格递增。恰好两个结点被交换后，序列里会出现一处或两处逆序：相邻交换只有一处，不相邻则有两处（第一处逆序的前者、第二处逆序的后者）。

因此中序走一遍，记下这两处，最后交换它们的值即可，不必重建树。本题采用递归中序，空间为 $O(n)$ 的递归栈；进阶若要 $O(1)$ 空间，可改用 Morris 遍历。此处先保证错误结点被正确找出。

中序遍历二叉搜索树，得到的序列是递增的。如果有两个节点的值被错误地交换，那么中序遍历得到的序列中，一定会出现两个逆序对。我们用 first 和 second 分别记录这两个逆序对中较小值和较大值的节点，最后交换这两个节点的值即可。

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

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func recoverTree(root *TreeNode) {
	var prev, first, second *TreeNode
	var dfs func(*TreeNode)
	dfs = func(root *TreeNode) {
		if root == nil {
			return
		}
		dfs(root.Left)
		if prev != nil && prev.Val > root.Val {
			if first == nil {
				first = prev
			}
			second = root
		}
		prev = root
		dfs(root.Right)
	}
	dfs(root)
	first.Val, second.Val = second.Val, first.Val
}

力扣原题 · Doocs 题解来源

100. 相同的树

简单2 种解法

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

题目、示例与约束

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

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

 

示例 1：

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

示例 2：

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

示例 3：

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

 

提示：

• 两棵树上的节点数目都在范围 [0, 100] 内
• -104 <= Node.val <= 104

方法一：DFS · Go 实现

思考

两棵树是否相同，取决于对应位置的结构与取值是否一致。若先各自遍历再比较序列，还要额外约定空位编码，实现更绕。节点数不超过 $100$，递归深度可以接受。

树由根与左右子树递归定义，因此只需比较当前一对节点：同为空则相同，仅一方为空或值不同则不同，否则分别递归左右孩子。

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

首先判断两个二叉树的根节点是否相同，如果两个根节点都为空，则两个二叉树相同，如果两个根节点中有且只有一个为空，则两个二叉树一定不同。如果两个根节点都不为空，则判断它们的值是否相同，如果不相同则两个二叉树一定不同，如果相同，则分别判断两个二叉树的左子树是否相同以及右子树是否相同。当以上所有条件都满足时，两个二叉树才相同。

时间复杂度 $O(min(m,n))$，空间复杂度 $O(min(m,n))$。其中 $m$ 和 $n$ 分别是两个二叉树的节点个数。空间复杂度主要取决于递归调用的层数，递归调用的层数不会超过较小的二叉树的节点个数。

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

方法二：BFS · Go 实现

思考

方法一已经给出结果，代价是系统递归栈。若改为迭代，需要按相同顺序同步访问两棵树。层序队列可以成对取出节点比较取值与孩子是否存在，再把对应孩子成对入队，不再使用递归。

我们也可以使用 BFS 迭代的方法来解决这个问题。

首先将两个二叉树的根节点分别加入两个队列。每次从两个队列各取出一个节点，进行如下比较操作。如果两个节点的值不相同，则两个二叉树的结构一定不同，如果两个节点的值相同，则判断两个节点的子节点是否为空，如果只有一个节点的左子节点为空，则两个二叉树的结构一定不同，如果只有一个节点的右子节点为空，则两个二叉树的结构一定不同，如果左右子节点的结构相同，则将两个节点的左子节点和右子节点分别加入两个队列，对于下一次迭代，将从两个队列各取出一个节点进行比较。当两个队列同时为空时，说明我们已经比较完了所有节点，两个二叉树的结构完全相同。

时间复杂度 $O(min(m,n))$，空间复杂度 $O(min(m,n))$。其中 $m$ 和 $n$ 分别是两个二叉树的节点个数。空间复杂度主要取决于队列中的元素个数，队列中的元素个数不会超过较小的二叉树的节点个数。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSameTree(p *TreeNode, q *TreeNode) bool {
	if p == q {
		return true
	}
	if p == nil || q == nil {
		return false
	}
	q1 := []*TreeNode{p}
	q2 := []*TreeNode{q}
	for len(q1) > 0 && len(q2) > 0 {
		p, q = q1[0], q2[0]
		if p.Val != q.Val {
			return false
		}
		q1, q2 = q1[1:], q2[1:]
		la, ra := p.Left, p.Right
		lb, rb := q.Left, q.Right
		if (la != nil && lb == nil) || (lb != nil && la == nil) {
			return false
		}
		if (ra != nil && rb == nil) || (rb != nil && ra == nil) {
			return false
		}
		if la != nil {
			q1 = append(q1, la)
			q2 = append(q2, lb)
		}
		if ra != nil {
			q1 = append(q1, ra)
			q2 = append(q2, rb)
		}
	}
	return true
}

力扣原题 · Doocs 题解来源

101. 对称二叉树

简单1 种解法

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

题目、示例与约束

给你一个二叉树的根节点 root ， 检查它是否轴对称。

 

示例 1：

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

示例 2：

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

 

提示：

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

 

进阶：你可以运用递归和迭代两种方法解决这个问题吗？

方法一：递归 · Go 实现

思考

镜像对称要求左子树与右子树互为镜像，而不是各自与自身相同。进阶同时要求递归与迭代都能做； $n\le 1000$，一次遍历即可。

一对节点对称，当且仅当取值相同，且一方的左孩子与另一方的右孩子对称、一方的右孩子与另一方的左孩子对称。因此从根的左右孩子出发做交叉递归即可。

我们设计一个函数 $\mathit{\text{dfs}}(\mathit{\text{root1}},\mathit{\text{root2}})$，用于判断两个二叉树是否对称。答案即为 $\mathit{\text{dfs}}(\mathit{\text{root.left}},\mathit{\text{root.right}})$。

函数 $\mathit{\text{dfs}}(\mathit{\text{root1}},\mathit{\text{root2}})$ 的逻辑如下：

• 如果 $\mathit{\text{root1}}$ 和 $\mathit{\text{root2}}$ 都为空，则两个二叉树对称，返回 true；
• 如果 $\mathit{\text{root1}}$ 和 $\mathit{\text{root2}}$ 中只有一个为空，或者 $\mathit{\text{root1.val}}\ne \mathit{\text{root2.val}}$
• 否则，判断 $\mathit{\text{root1}}$ 的左子树和 $\mathit{\text{root2}}$ 的右子树是否对称，以及 $\mathit{\text{root1}}$ 的右子树和 $\mathit{\text{root2}}$ 的左子树是否对称，这里使用了递归。

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

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

力扣原题 · Doocs 题解来源

102. 二叉树的层序遍历

中等1 种解法

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

题目、示例与约束

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

 

示例 1：

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

示例 2：

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

示例 3：

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

 

提示：

• 树中节点数目在范围 [0, 2000] 内
• -1000 <= Node.val <= 1000

方法一：BFS · Go 实现

思考

题目要按层输出节点值。深度优先也能记下深度再分组，但同一层的左右顺序还要额外整理。 $n\le 2000$，一层最多 $O(n)$ 个节点。

广度优先天然按层扩张：队列中当前一批节点恰为一层，出队时收集取值并压入孩子，即可得到从左到右的一层结果。

我们可以使用 BFS 的方法来解决这道题。首先将根节点入队，然后不断地进行以下操作，直到队列为空：

• 遍历当前队列中的所有节点，将它们的值存储到一个临时数组 $t$ 中，然后将它们的孩子节点入队。
• 将临时数组 $t$ 存储到答案数组中。

最后返回答案数组即可。

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

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

力扣原题 · Doocs 题解来源

103. 二叉树的锯齿形层序遍历

中等1 种解法

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

题目、示例与约束

给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

 

示例 1：

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

示例 2：

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

示例 3：

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

 

提示：

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

方法一：BFS · Go 实现

思考

与普通层序相比，奇数层仍从左到右，偶数层要从右到左。若按层建好后再整体反转部分层，时间仍是 $O(n)$。 $n\le 2000$ 可以接受。

因此仍用队列做层序，额外用一个方向标志：本层收集完毕后，若当前方向为右到左，则反转该层再写入答案，并翻转标志。孩子始终按从左到右入队，下一层的遍历顺序不受影响。

为了实现锯齿形层序遍历，需要在层序遍历的基础上增加一个标志位 left，用于标记当前层的节点值的顺序。如果 left 为 true，则当前层的节点值按照从左到右的顺序存入结果数组 ans 中；如果 left 为 false，则当前层的节点值按照从右到左的顺序存入结果数组 ans 中。

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

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

力扣原题 · Doocs 题解来源

104. 二叉树的最大深度

简单1 种解法

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

题目、示例与约束

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

 

示例 1：

 

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

示例 2：

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

 

提示：

• 树中节点的数量在 [0, 104] 区间内。
• -100 <= Node.val <= 100

方法一：递归 · Go 实现

思考

树的深度是根到最远叶子的边数加一。层序统计层数可行， $n\le {10}^4$ 时间足够。树本身按递归定义，当前树的深度等于左右子树深度的较大值再加一，空树深度为 $0$。为此对左右子树递归求深度后取最大即可。

递归遍历左右子树，求左右子树的最大深度，然后取最大值加 $1$ 即可。

时间复杂度 $O(n)$，其中 $n$ 是二叉树的节点数。每个节点在递归中只被遍历一次。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func maxDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}
	l, r := maxDepth(root.Left), maxDepth(root.Right)
	return 1 + max(l, r)
}

力扣原题 · Doocs 题解来源

105. 从前序与中序遍历序列构造二叉树

中等2 种解法

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

题目、示例与约束

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

 

示例 1:

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

示例 2:

输入: preorder = [-1], inorder = [-1]
输出: [-1]

 

提示:

• 1 <= preorder.length <= 3000
• inorder.length == preorder.length
• -3000 <= preorder[i], inorder[i] <= 3000
• preorder 和 inorder 均 无重复 元素
• inorder 均出现在 preorder
• preorder 保证 为二叉树的前序遍历序列
• inorder 保证 为二叉树的中序遍历序列

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

思考

前序给出根的出现顺序，中序给出每个根左右子树的分界。每次在中序里线性扫描根的位置，总时间可达 $O(n^2)$； $n\le 3000$ 偏紧。

题目保证节点值互不相同，因此中序位置可以预处理进哈希表，查找变为 $O(1)$。前序区间的首元素是根，中序中该值左侧是左子树、右侧是右子树，长度确定后再递归构造两段。

前序序列的第一个节点 $preorder[0]$ 为根节点，我们在中序序列中找到根节点的位置 $k$，可以将中序序列划分为左子树 $inorder[0..k]$ 、右子树 $inorder[k+1..]$。

通过左右子树的区间，可以计算出左、右子树节点的个数，假设为 $a$ 和 $b$。然后在前序节点中，从根节点往后的 $a$ 个节点为左子树，再往后的 $b$ 个节点为右子树。

因此，我们设计一个函数 $dfs(i,j,n)$，其中 $i$ 和 $j$ 分别表示前序序列和中序序列的起始位置，而 $n$ 表示节点个数。函数的返回值是以 $preorder[i..i+n-1]$ 为前序序列，以 $inorder[j..j+n-1]$ 为中序序列构造出的二叉树。

函数 $dfs(i,j,n)$ 的执行过程如下：

• 如果 $n\le 0$，说明没有节点，返回空节点。
• 取出前序序列的第一个节点 $v=preorder[i]$ 作为根节点，然后利用哈希表 $d$ 找到根节点在中序序列中的位置 $k$，那么左子树的节点个数为 $k-j$，右子树的节点个数为 $n-k+j-1$。
• 递归构造左子树 $l=dfs(i+1,j,k-j)$ 和右子树 $r=dfs(i+1+k-j,k+1,n-k+j-1)$。
• 最后返回以 $v$ 为根节点且左右子树分别为 $l$ 和 $r$ 的二叉树。

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

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

方法二：哈希表 + 递归（节点值可重复） · Go 实现

思考

方法一依赖「值唯一」才能用单个下标定位根。若值可重复，同一值在中序中可能有多个合法位置，必须记录全部下标并枚举落在当前区间内的每一个，分别递归左右子树再做笛卡尔组合。本题本身不需要这条分支，它回答的是值可重复时如何穷举所有可行树。

本题保证节点值互不相同。如果节点值可以重复，哈希表需要记录每个值出现的所有位置，并枚举当前区间内每一个可能的根位置，递归构造出所有可能的二叉树。

时间复杂度和空间复杂度均与可行二叉树的数量相关（需要构造并保存全部结果），最坏情况下为指数级。递归栈额外占用 $O(n)$ 空间。

func getBinaryTrees(preOrder []int, inOrder []int) []*TreeNode {
	n := len(preOrder)
	d := map[int][]int{}
	for i, x := range inOrder {
		d[x] = append(d[x], i)
	}
	var dfs func(i, j, n int) []*TreeNode
	dfs = func(i, j, n int) []*TreeNode {
		ans := []*TreeNode{}
		if n <= 0 {
			ans = append(ans, nil)
			return ans
		}
		v := preOrder[i]
		for _, k := range d[v] {
			if k >= j && k < j+n {
				lefts := dfs(i+1, j, k-j)
				rights := dfs(i+1+k-j, k+1, n-1-(k-j))
				for _, left := range lefts {
					for _, right := range rights {
						ans = append(ans, &TreeNode{v, left, right})
					}
				}
			}
		}
		return ans
	}
	return dfs(0, 0, n)
}

力扣原题 · Doocs 题解来源

106. 从中序与后序遍历序列构造二叉树

中等1 种解法

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

题目、示例与约束

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

 

示例 1:

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

示例 2:

输入：inorder = [-1], postorder = [-1]
输出：[-1]

 

提示:

• 1 <= inorder.length <= 3000
• postorder.length == inorder.length
• -3000 <= inorder[i], postorder[i] <= 3000
• inorder 和 postorder 都由 不同 的值组成
• postorder 中每一个值都在 inorder 中
• inorder 保证是树的中序遍历
• postorder 保证是树的后序遍历

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

思考

后序的最后一个元素是根，中序同样给出左右子树的分界。每次线性查找根的位置仍可能 $O(n^2)$。值互不相同，因此先把中序下标放入哈希表。当前后序区间的末元素为根，中序中该值左侧长度即左子树规模，据此切分两段后序并递归。

后序遍历的最后一个节点是根节点，我们可以根据这个特点找到根节点在中序遍历中的位置，然后递归地构造左右子树。

具体地，我们先用一个哈希表 $d$ 存储中序遍历中每个节点的位置。然后我们设计一个递归函数 $dfs(i,j,n)$，其中 $i$ 和 $j$ 分别表示中序遍历和后序遍历的起点，而 $n$ 表示子树包含的节点数。函数的逻辑如下：

• 如果 $n\le 0$，说明子树为空，返回空节点。
• 否则，取出后序遍历的最后一个节点 $v$，然后我们在哈希表 $d$ 中找到 $v$ 在中序遍历中的位置，设为 $k$。那么左子树包含的节点数为 $k-i$，右子树包含的节点数为 $n-k+i-1$。
• 递归构造左子树 $dfs(i,j,k-i)$ 和右子树 $dfs(k+1,j+k-i,n-k+i-1)$，并连接到根节点上，最后返回根节点。

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

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func buildTree(inorder []int, postorder []int) *TreeNode {
	d := map[int]int{}
	for i, v := range inorder {
		d[v] = i
	}
	var dfs func(i, j, n int) *TreeNode
	dfs = func(i, j, n int) *TreeNode {
		if n <= 0 {
			return nil
		}
		v := postorder[j+n-1]
		k := d[v]
		l := dfs(i, j, k-i)
		r := dfs(k+1, j+k-i, n-k+i-1)
		return &TreeNode{v, l, r}
	}
	return dfs(0, 0, len(inorder))
}

力扣原题 · Doocs 题解来源

107. 二叉树的层序遍历 II

中等1 种解法

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

题目、示例与约束

给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

 

示例 1：

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

示例 2：

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

示例 3：

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

 

提示：

• 树中节点数目在范围 [0, 2000] 内
• -1000 <= Node.val <= 1000

方法一：BFS · Go 实现

思考

与层序遍历相比，只是要求自底向上输出。先按层收集再整体反转，不必在遍历时插入到数组头部。 $n\le 2000$，BFS 一层一批出队即可，最后将答案数组倒序返回。

我们可以使用 BFS 的方法来解决这道题。首先将根节点入队，然后不断地进行以下操作，直到队列为空：

• 遍历当前队列中的所有节点，将它们的值存储到一个临时数组 $t$ 中，然后将它们的孩子节点入队。
• 将临时数组 $t$ 存储到答案数组中。

最后将答案数组反转后返回即可。

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

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func levelOrderBottom(root *TreeNode) (ans [][]int) {
	if root == nil {
		return
	}
	q := []*TreeNode{root}
	for len(q) > 0 {
		t := []int{}
		for n := len(q); n > 0; n-- {
			node := q[0]
			q = q[1:]
			t = append(t, node.Val)
			if node.Left != nil {
				q = append(q, node.Left)
			}
			if node.Right != nil {
				q = append(q, node.Right)
			}
		}
		ans = append(ans, t)
	}
	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 题解来源

108. 将有序数组转换为二叉搜索树

简单1 种解法

标签：树、二叉搜索树、数组、分治、二叉树

题目、示例与约束

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树。

 

示例 1：

输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

示例 2：

输入：nums = [1,3]
输出：[3,1]
解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。

 

提示：

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums 按 严格递增 顺序排列

方法一：二分 + 递归 · Go 实现

思考

有序数组本身就是一棵 BST 的中序序列。若总取左端或右端为根，树会退化成链，高度为 $n$，不满足高度平衡。 $n\le {10}^4$。

区间中点作为根时，左右两侧元素个数至多相差 $1$，子树高度自然平衡。为此在 $[l,r]$ 上取中点建根，再递归左右半段。

我们设计一个递归函数 $\mathit{\text{dfs}}(l,r)$，表示当前待构造的二叉搜索树的节点值都在数组 $\mathit{\text{nums}}$ 的下标范围 $[l,r]$ 内。该函数返回构造出的二叉搜索树的根节点。

函数 $\mathit{\text{dfs}}(l,r)$ 的执行流程如下：

1. 如果 $l>r$，说明当前数组为空，返回 null。
2. 如果 $l\le r$，取数组中下标为 $\mathit{\text{mid}}=\lfloor \frac{l+r}{2}\rfloor$ 的元素作为当前二叉搜索树的根节点，其中 $\lfloor x\rfloor$ 表示对 $x$ 向下取整。
3. 递归地构造当前二叉搜索树的左子树，其根节点的值为数组中下标为 $\mathit{\text{mid}}-1$ 的元素，左子树的节点值都在数组的下标范围 $[l,\mathit{\text{mid}}-1]$ 内。
4. 递归地构造当前二叉搜索树的右子树，其根节点的值为数组中下标为 $\mathit{\text{mid}}+1$ 的元素，右子树的节点值都在数组的下标范围 $[\mathit{\text{mid}}+1,r]$ 内。
5. 返回当前二叉搜索树的根节点。

答案即为函数 $\mathit{\text{dfs}}(0,n-1)$ 的返回值。

时间复杂度 $O(n)$，空间复杂度 $O(\log n)$。其中 $n$ 为数组 $\mathit{\text{nums}}$ 的长度。

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

力扣原题 · Doocs 题解来源

109. 有序链表转换二叉搜索树

中等1 种解法

标签：树、二叉搜索树、链表、分治、二叉树

题目、示例与约束

给定一个单链表的头节点  head ，其中的元素 按升序排序 ，将其转换为 平衡 二叉搜索树。

 

示例 1:

输入: head = [-10,-3,0,5,9]
输出: [0,-3,9,-10,null,5]
解释: 一个可能的答案是[0，-3,9，-10,null,5]，它表示所示的高度平衡的二叉搜索树。

示例 2:

输入: head = []
输出: []

 

提示:

• head 中的节点数在[0, 2 * 104] 范围内
• -105 <= Node.val <= 105

方法一：DFS · Go 实现

思考

链表不能按下标 $O(1)$ 取中点，若每次快慢指针找中点再递归，时间是 $O(n\log n)$。节点数可达 $2\times {10}^4$。

有序链表与有序数组一样对应中序序列。先线性扫成数组，之后与「有序数组建平衡 BST」相同：取区间中点为根并递归两侧。额外 $O(n)$ 空间换来每次 $O(1)$ 定位中点。

我们先将链表转换为数组 $\mathit{\text{nums}}$，然后使用深度优先搜索构造二叉搜索树。

我们定义一个函数 $\mathit{\text{dfs}}(i,j)$，其中 $i$ 和 $j$ 表示当前区间为 $[i,j]$。每次我们选择区间中间位置 $\mathit{\text{mid}}$ 的数字作为根节点，递归地构造左侧区间 $[i,\mathit{\text{mid}}-1]$ 的子树，以及右侧区间 $[\mathit{\text{mid}}+1,j]$ 的子树。最后返回 $\mathit{\text{mid}}$ 对应的节点作为当前子树的根节点。

在主函数中，我们只需要调用 $\mathit{\text{dfs}}(0,n-1)$ 并返回即可。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 是链表的长度。

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sortedListToBST(head *ListNode) *TreeNode {
	nums := []int{}
	for ; head != nil; head = head.Next {
		nums = append(nums, head.Val)
	}
	var dfs func(i, j int) *TreeNode
	dfs = func(i, j int) *TreeNode {
		if i > j {
			return nil
		}
		mid := (i + j) >> 1
		left := dfs(i, mid-1)
		right := dfs(mid+1, j)
		return &TreeNode{nums[mid], left, right}
	}
	return dfs(0, len(nums)-1)
}

力扣原题 · Doocs 题解来源

110. 平衡二叉树

简单1 种解法

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

题目、示例与约束

给定一个二叉树，判断它是否是 平衡二叉树  

 

示例 1：

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

示例 2：

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

示例 3：

输入：root = []
输出：true

 

提示：

• 树中的节点数在范围 [0, 5000] 内
• -104 <= Node.val <= 104

方法一：自底向上的递归 · Go 实现

思考

若对每个节点单独再算一遍左右高度，同一子树会被重复访问，最坏 $O(n^2)$； $n\le 5000$ 偏紧。

平衡性可以由高度顺便判定：自底向上返回高度，若某棵子树已不平衡则向上传递失败标记。一次后序遍历即可同时得到高度与是否平衡。

定义函数 $height(root)$ 计算二叉树的高度，处理逻辑如下：

• 如果二叉树 $root$ 为空，返回 $0$。
• 否则，递归计算左右子树的高度，分别为 $l$ 和 $r$。如果 $l$ 或 $r$ 为 $-1$，或者 $l$ 和 $r$ 的差的绝对值大于 $1$，则返回 $-1$，否则返回 $max(l,r)+1$。

那么，如果函数 $height(root)$ 返回的是 $-1$，则说明二叉树 $root$ 不是平衡二叉树，否则是平衡二叉树。

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

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isBalanced(root *TreeNode) bool {
	var height func(*TreeNode) int
	height = func(root *TreeNode) int {
		if root == nil {
			return 0
		}
		l, r := height(root.Left), height(root.Right)
		if l == -1 || r == -1 || abs(l-r) > 1 {
			return -1
		}
		if l > r {
			return 1 + l
		}
		return 1 + r
	}
	return height(root) >= 0
}

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

力扣原题 · Doocs 题解来源

111. 二叉树的最小深度

简单2 种解法

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

题目、示例与约束

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

 

示例 1：

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

示例 2：

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

 

提示：

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

方法一：递归 · Go 实现

思考

最小深度是根到最近叶子的节点数。注意「只有一侧孩子」的节点不是叶子，必须继续走向仅有的那一侧，否则会把缺失的孩子当成深度 $0$。 $n\le {10}^5$。

递归时：空树为 $0$；缺左则 $1$ 加上右子树最小深度；缺右同理；两侧都在则取较小者加 $1$。

递归的终止条件是当前节点为空，此时返回 $0$；如果当前节点左右子树有一个为空，返回不为空的子树的最小深度加 $1$；如果当前节点左右子树都不为空，返回左右子树最小深度的较小值加 $1$。

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

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func minDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}
	if root.Left == nil {
		return 1 + minDepth(root.Right)
	}
	if root.Right == nil {
		return 1 + minDepth(root.Left)
	}
	return 1 + min(minDepth(root.Left), minDepth(root.Right))
}

方法二：BFS · Go 实现

思考

方法一可能先走完整棵深树才遇到最近叶子。最小深度对应最短路径，BFS 按层扩张，第一次到达叶子即可停止，偏斜树时常数更好。

使用队列实现广度优先搜索，初始时将根节点加入队列。每次从队列中取出一个节点，如果该节点是叶子节点，则直接返回当前深度；如果该节点不是叶子节点，则将该节点的所有非空子节点加入队列。继续搜索下一层节点，直到找到叶子节点。

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

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

力扣原题 · Doocs 题解来源

112. 路径总和

简单1 种解法

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

题目、示例与约束

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

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

 

示例 1：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解释：等于目标和的根节点到叶节点路径如上图所示。

示例 2：

输入：root = [1,2,3], targetSum = 5
输出：false
解释：树中存在两条根节点到叶子节点的路径：
(1 --> 2): 和为 3
(1 --> 3): 和为 4
不存在 sum = 5 的根节点到叶子节点的路径。

示例 3：

输入：root = [], targetSum = 0
输出：false
解释：由于树是空的，所以不存在根节点到叶子节点的路径。

 

提示：

• 树中节点的数目在范围 [0, 5000] 内
• -1000 <= Node.val <= 1000
• -1000 <= targetSum <= 1000

方法一：递归 · Go 实现

思考

需要判断是否存在根到叶子的路径，其节点和等于目标。枚举所有路径再求和， $n\le 5000$ 可行，但路径复制有额外开销。

沿递归向下累加当前和，只有到达叶子时才判断是否命中。左右两边有一边成功即可，不必保存整条路径。

从根节点开始，递归地对树进行遍历，并在遍历过程中更新节点的值为从根节点到该节点的路径和。当遍历到叶子节点时，判断该路径和是否等于目标值，如果相等则返回 true，否则返回 false。

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

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func hasPathSum(root *TreeNode, targetSum int) bool {
	var dfs func(*TreeNode, int) bool
	dfs = func(root *TreeNode, s int) bool {
		if root == nil {
			return false
		}
		s += root.Val
		if root.Left == nil && root.Right == nil && s == targetSum {
			return true
		}
		return dfs(root.Left, s) || dfs(root.Right, s)
	}
	return dfs(root, 0)
}

力扣原题 · Doocs 题解来源

113. 路径总和 II

中等1 种解法

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

题目、示例与约束

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

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

 

示例 1：

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

示例 2：

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

示例 3：

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

 

提示：

• 树中节点总数在范围 [0, 5000] 内
• -1000 <= Node.val <= 1000
• -1000 <= targetSum <= 1000

方法一：DFS · Go 实现

思考

与「路径总和」不同，这里要列出每一条和为 $\mathit{\text{targetSum}}$ 的根到叶子路径。 $n\le 5000$，最坏每条路径都要复制进答案，时间可达 $O(n^2)$。

深度优先向下走时把节点压入当前路径并累加和，到达叶子且和相等则拷贝一份；回溯时弹出，以便左右分支共用同一缓冲区。

我们从根节点开始，递归遍历所有从根节点到叶子节点的路径，并记录路径和。当遍历到叶子节点时，如果此时路径和等于 targetSum，则将此路径加入答案。

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

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

力扣原题 · Doocs 题解来源

114. 二叉树展开为链表

中等2 种解法

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

题目、示例与约束

给你二叉树的根结点 root ，请你将它展开为一个单链表：

• 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
• 展开后的单链表应该与二叉树 先序遍历 顺序相同。

 

示例 1：

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

示例 2：

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

示例 3：

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

 

提示：

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

 

进阶：你可以使用原地算法（O(1) 额外空间）展开这棵树吗？

方法一：寻找前驱节点 · Go 实现

思考

先序展开可以用递归或栈先建出新链，但进阶要求 $O(1)$ 额外空间且原地修改。 $n\le 2000$。

先序中，左子树走完后的下一个节点就是原右子树的根。左子树最右节点恰是这段的前驱：把它的右指针接到原右子树，再把左子树整体接到当前右指针上并清空左指针。沿右链继续，无需递归栈。

先序遍历的访问顺序是“根、左子树、右子树”，左子树最后一个节点访问完后，接着会访问根节点的右子树节点。

因此，对于当前节点，如果其左子节点不为空，我们找到左子树的最右节点，作为前驱节点，然后将当前节点的右子节点赋给前驱节点的右子节点。然后将当前节点的左子节点赋给当前节点的右子节点，并将当前节点的左子节点置为空。然后将当前节点的右子节点作为下一个节点，继续处理，直至所有节点处理完毕。

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

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func flatten(root *TreeNode) {
	for root != nil {
		if root.Left != nil {
			pre := root.Left
			for pre.Right != nil {
				pre = pre.Right
			}
			pre.Right = root.Right
			root.Right = root.Left
			root.Left = nil
		}
		root = root.Right
	}
}

方法二 · Go 实现

思考

方法一已经是 $O(1)$ 空间的前驱拼接。本写法只是同一过程的另一种实现：先取出左右孩子，再把左子树接到右侧、最右节点接回原右子树，沿右指针前进。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func flatten(root *TreeNode) {
	for root != nil {
		left, right := root.Left, root.Right
		root.Left = nil
		if left != nil {
			root.Right = left
			for left.Right != nil {
				left = left.Right
			}
			left.Right = right
		}
		root = root.Right
	}
}

力扣原题 · Doocs 题解来源

116. 填充每个节点的下一个右侧节点指针

中等2 种解法

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

题目、示例与约束

给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

 

示例 1：

输入：root = [1,2,3,4,5,6,7]
输出：[1,#,2,3,#,4,5,6,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化的输出按层序遍历排列，同一层节点由 next 指针连接，'#' 标志着每一层的结束。

示例 2:

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

 

提示：

• 树中节点的数量在 [0, 212 - 1] 范围内
• -1000 <= node.val <= 1000

 

进阶：

• 你只能使用常量级额外空间。
• 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。

方法一：BFS · Go 实现

思考

完美二叉树的每一层都是满的，层序时把同一层相邻节点用 $\mathit{\text{next}}$ 串起来即可。 $n<2^{12}$，队列空间与一层宽度同阶。进阶要求常数额外空间，方法一先给出正确的层序连法。

使用队列进行层序遍历，每次遍历一层时，将当前层的节点按顺序连接起来。

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

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

func connect(root *Node) *Node {
	if root == nil {
		return root
	}
	q := []*Node{root}
	for len(q) > 0 {
		var p *Node
		for n := len(q); n > 0; n-- {
			node := q[0]
			q = q[1:]
			if p != nil {
				p.Next = node
			}
			p = node
			if node.Left != nil {
				q = append(q, node.Left)
			}
			if node.Right != nil {
				q = append(q, node.Right)
			}
		}
	}
	return root
}

方法二：DFS · Go 实现

思考

方法一要用队列保存整层。完美二叉树中，一个节点的左右孩子相邻，右孩子的下一个是兄弟的左孩子。父层的 $\mathit{\text{next}}$ 已经连好，可以当作遍历下一层的线索，递归把相邻指针接上，不再需要队列。

使用递归进行前序遍历，每次遍历到一个节点时，将其左右子节点按顺序连接起来。

具体地，我们设计一个函数 $dfs(left,right)$，表示将 $left$ 节点的 $next$ 指针指向 $right$ 节点。在函数中，我们首先判断 $left$ 和 $right$ 是否为空，若都不为空，则将 $left.next$ 指向 $right$，然后递归地调用 $dfs(left.left,left.right)$, $dfs(left.right,right.left)$, $dfs(right.left,right.right)$。

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

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

func connect(root *Node) *Node {
	var dfs func(*Node, *Node)
	dfs = func(left, right *Node) {
		if left == nil || right == nil {
			return
		}
		left.Next = right
		dfs(left.Left, left.Right)
		dfs(left.Right, right.Left)
		dfs(right.Left, right.Right)
	}
	if root != nil {
		dfs(root.Left, root.Right)
	}
	return root
}

力扣原题 · Doocs 题解来源

117. 填充每个节点的下一个右侧节点指针 II

中等2 种解法

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

题目、示例与约束

给定一个二叉树：

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL 。

初始状态下，所有 next 指针都被设置为 NULL 。

 

示例 1：

输入：root = [1,2,3,4,5,null,7]
输出：[1,#,2,3,#,4,5,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化输出按层序遍历顺序（由 next 指针连接），'#' 表示每层的末尾。

示例 2：

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

 

提示：

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

进阶：

• 你只能使用常量级额外空间。
• 使用递归解题也符合要求，本题中递归程序的隐式栈空间不计入额外空间复杂度。

方法一：BFS · Go 实现

思考

与上一题不同，树不必是完美的，一层里孩子可能缺失，不能默认「左孩子 next 指向右孩子」。层序仍然正确：按层出队，把相邻节点依次接上。 $n\le 6000$。

我们使用队列 $q$ 进行层序遍历，每次遍历一层时，将当前层的节点按顺序连接起来。

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

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

func connect(root *Node) *Node {
	if root == nil {
		return root
	}
	q := []*Node{root}
	for len(q) > 0 {
		var p *Node
		for n := len(q); n > 0; n-- {
			node := q[0]
			q = q[1:]
			if p != nil {
				p.Next = node
			}
			p = node
			if node.Left != nil {
				q = append(q, node.Left)
			}
			if node.Right != nil {
				q = append(q, node.Right)
			}
		}
	}
	return root
}

方法二：空间优化 · Go 实现

思考

方法一的队列与一层宽度同阶，进阶要 $O(1)$ 空间。当前层的 $\mathit{\text{next}}$ 已是一条链表，遍历它时可以把下一层的非空孩子按出现顺序串起来，并记下下一层的头。一层结束后改走这一条新链，不再使用队列。

方法一的空间复杂度较高，因为需要使用队列存储每一层的节点。我们可以使用常数空间来实现。

定义两个指针 $prev$ 和 $next$，分别指向下一层的前一个节点和第一个节点。遍历当前层的节点时，把下一层的节点串起来，同时找到下一层的第一个节点。当前层遍历完后，把下一层的第一个节点 $next$ 赋值给 $node$，继续遍历。

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

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

func connect(root *Node) *Node {
	node := root
	var prev, next *Node
	modify := func(curr *Node) {
		if curr == nil {
			return
		}
		if next == nil {
			next = curr
		}
		if prev != nil {
			prev.Next = curr
		}
		prev = curr
	}
	for node != nil {
		prev, next = nil, nil
		for node != nil {
			modify(node.Left)
			modify(node.Right)
			node = node.Next
		}
		node = next
	}
	return root
}

力扣原题 · Doocs 题解来源

124. 二叉树中的最大路径和

困难1 种解法

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

题目、示例与约束

二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

 

示例 1：

输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6

示例 2：

输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42

 

提示：

• 树中节点数目范围是 [1, 3 * 104]
• -1000 <= Node.val <= 1000

方法一：递归 · Go 实现

思考

路径可以经过任意节点，不必过根，也可以在某节点「拐弯」同时走左右子树。枚举所有路径在 $n\le 3\times {10}^4$ 下不可行。

对每个节点，能向上贡献的只是「节点值加上左右中较大的一条非负链」；左右都接上的和只用于更新全局答案，不能再往上传。负贡献应丢弃，因此递归返回前对子树结果与 $0$ 取最大。

我们思考二叉树递归问题的经典套路：

1. 终止条件（何时终止递归）
2. 递归处理左右子树
3. 合并左右子树的计算结果

对于本题，我们设计一个函数 $dfs(root)$，它返回以 $root$ 为根节点的二叉树的最大路径和。

函数 $dfs(root)$ 的执行逻辑如下：

如果 $root$ 不存在，那么 $dfs(root)$ 返回 $0$；

否则，我们递归计算 $root$ 的左子树和右子树的最大路径和，分别记为 $left$ 和 $right$。如果 $left$ 小于 $0$，那么我们将其置为 $0$，同理，如果 $right$ 小于 $0$，那么我们将其置为 $0$。

然后，我们用 $root.val+left+right$ 更新答案。最后，函数返回 $root.val+max(left,right)$。

在主函数中，我们调用 $dfs(root)$，即可得到每个节点的最大路径和，其中的最大值即为答案。

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

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

力扣原题 · Doocs 题解来源

129. 求根节点到叶节点数字之和

中等1 种解法

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

题目、示例与约束

给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。

每条从根节点到叶节点的路径都代表一个数字：

• 例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。

计算从根节点到叶节点生成的 所有数字之和 。

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

 

示例 1：

输入：root = [1,2,3]
输出：25
解释：
从根到叶子节点路径 1->2 代表数字 12
从根到叶子节点路径 1->3 代表数字 13
因此，数字总和 = 12 + 13 = 25

示例 2：

输入：root = [4,9,0,5,1]
输出：1026
解释：
从根到叶子节点路径 4->9->5 代表数字 495
从根到叶子节点路径 4->9->1 代表数字 491
从根到叶子节点路径 4->0 代表数字 40
因此，数字总和 = 495 + 491 + 40 = 1026

 

提示：

• 树中节点的数目在范围 [1, 1000] 内
• 0 <= Node.val <= 9
• 树的深度不超过 10

方法一：DFS · Go 实现

思考

每条根到叶子路径表示一个整数，求这些整数之和。深度不超过 $10$，路径不多，但不必先把数字转成字符串。向下走时用 $s\times 10+\mathit{\text{val}}$ 累加当前数，到叶子把该数加入答案，左右子树的和相加即可。

我们可以设计一个函数 $dfs(root,s)$，表示从当前节点 $root$ 出发，且当前路径数字为 $s$，返回从当前节点到叶子节点的所有路径数字之和。那么答案就是 $dfs(root,0)$。

函数 $dfs(root,s)$ 的计算如下：

• 如果当前节点 $root$ 为空，则返回 $0$。
• 否则，将当前节点的值加到 $s$ 中，即 $s=s\times 10+root.val$。
• 如果当前节点是叶子节点，则返回 $s$。
• 否则，返回 $dfs(root.left,s)+dfs(root.right,s)$。

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

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

力扣原题 · Doocs 题解来源

144. 二叉树的前序遍历

简单3 种解法

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

题目、示例与约束

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

 

示例 1：

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

输出：[1,2,3]

解释：

示例 2：

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

输出：[1,2,4,5,6,7,3,8,9]

解释：

示例 3：

输入：root = []

输出：[]

示例 4：

输入：root = [1]

输出：[1]

 

提示：

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

 

进阶：递归算法很简单，你可以通过迭代算法完成吗？

方法一：递归遍历 · Go 实现

思考

前序是「根、左、右」。树按递归定义，先记录根再递归左右即可。 $n\le 100$，递归栈可以接受。进阶才要求改成迭代。

我们先访问根节点，然后递归左子树和右子树。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 是二叉树的节点数，空间复杂度主要取决于递归调用的栈空间。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func preorderTraversal(root *TreeNode) (ans []int) {
	var dfs func(*TreeNode)
	dfs = func(root *TreeNode) {
		if root == nil {
			return
		}
		ans = append(ans, root.Val)
		dfs(root.Left)
		dfs(root.Right)
	}
	dfs(root)
	return
}

方法二：栈实现非递归遍历 · Go 实现

思考

方法一已经得到正确序列，进阶要去掉系统递归。显式栈先压右再压左，弹出时先处理根，顺序与前序相同，空间仍为 $O(n)$。

栈实现非递归遍历的思路如下：

1. 定义一个栈 $stk$，先将根节点压入栈
2. 若栈不为空，每次从栈中弹出一个节点
3. 处理该节点
4. 先把节点右孩子压入栈，接着把节点左孩子压入栈（如果有孩子节点）
5. 重复 2-4
6. 返回结果

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 是二叉树的节点数，空间复杂度主要取决于栈空间。

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

方法三：Morris 实现前序遍历 · Go 实现

思考

方法二仍把空间留在 $O(h)$。Morris 把左子树最右空指针临时接到当前根，沿左链走下去，第一次到达时输出根，回来再拆掉。树自身的空指针充当栈，空间 $O(1)$。

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

遍历二叉树节点，

1. 若当前节点 root 的左子树为空，将当前节点值添加至结果列表 $ans$ 中，并将当前节点更新为 root.right
2. 若当前节点 root 的左子树不为空，找到左子树的最右节点 pre（也即是 root 节点在中序遍历下的前驱节点）：
   • 若前驱节点 pre 的右子树为空，将当前节点值添加至结果列表 $ans$ 中，然后将前驱节点的右子树指向当前节点 root，并将当前节点更新为 root.left。
   • 若前驱节点 pre 的右子树不为空，将前驱节点右子树指向空（即解除 pre 与 root 的指向关系），并将当前节点更新为 root.right。
3. 循环以上步骤，直至二叉树节点为空，遍历结束。

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

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func preorderTraversal(root *TreeNode) (ans []int) {
	for root != nil {
		if root.Left == nil {
			ans = append(ans, root.Val)
			root = root.Right
		} else {
			prev := root.Left
			for prev.Right != nil && prev.Right != root {
				prev = prev.Right
			}
			if prev.Right == nil {
				ans = append(ans, root.Val)
				prev.Right = root
				root = root.Left
			} else {
				prev.Right = nil
				root = root.Right
			}
		}
	}
	return
}

力扣原题 · Doocs 题解来源

145. 二叉树的后序遍历

简单3 种解法

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

题目、示例与约束

给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。

 

示例 1：

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

输出：[3,2,1]

解释：

示例 2：

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

输出：[4,6,7,5,2,9,8,3,1]

解释：

示例 3：

输入：root = []

输出：[]

示例 4：

输入：root = [1]

输出：[1]

 

提示：

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

 

进阶：递归算法很简单，你可以通过迭代算法完成吗？

方法一：递归 · Go 实现

思考

后序是「左、右、根」。递归先走完左右再记录根。 $n\le 100$，递归栈可以接受。进阶要求迭代。

我们先递归左右子树，然后再访问根节点。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 是二叉树的节点数，空间复杂度主要取决于递归调用的栈空间。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func postorderTraversal(root *TreeNode) (ans []int) {
	var dfs func(*TreeNode)
	dfs = func(root *TreeNode) {
		if root == nil {
			return
		}
		dfs(root.Left)
		dfs(root.Right)
		ans = append(ans, root.Val)
	}
	dfs(root)
	return
}

方法二：栈实现后序遍历 · Go 实现

思考

方法一依赖递归。注意到「根、右、左」恰是前序交换左右孩子，再反转即得「左、右、根」。用栈按这个顺序遍历后整体倒序，不必判断节点是否第二次访问。

先序遍历的顺序是：根、左、右，如果我们改变左右孩子的顺序，就能将顺序变成：根、右、左。最后再将结果反转一下，就得到了后序遍历的结果。

因此，栈实现非递归遍历的思路如下：

1. 定义一个栈 $stk$，先将根节点压入栈
2. 若栈不为空，每次从栈中弹出一个节点
3. 处理该节点
4. 先把节点左孩子压入栈，接着把节点右孩子压入栈（如果有孩子节点）
5. 重复 2-4
6. 将结果反转，得到后序遍历的结果

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 是二叉树的节点数，空间复杂度主要取决于栈空间。

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

方法三：Morris 实现后序遍历 · Go 实现

思考

方法二仍要 $O(n)$ 栈与一次反转。Morris 按「根、右、左」穿针，最后再反转结果，额外空间降为 $O(1)$。

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

遍历二叉树节点，

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

Morris 后序遍历跟 Morris 前序遍历思路一致，只是将前序的“根左右”变为“根右左”，最后逆序结果即可变成“左右根”。

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

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func postorderTraversal(root *TreeNode) (ans []int) {
	for root != nil {
		if root.Right == nil {
			ans = append([]int{root.Val}, ans...)
			root = root.Left
		} else {
			next := root.Right
			for next.Left != nil && next.Left != root {
				next = next.Left
			}
			if next.Left == nil {
				ans = append([]int{root.Val}, ans...)
				next.Left = root
				root = root.Right
			} else {
				next.Left = nil
				root = root.Left
			}
		}
	}
	return
}

力扣原题 · Doocs 题解来源

156. 上下翻转二叉树 🔒

中等1 种解法

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

题目、示例与约束

给你一个二叉树的根节点 root ，请你将此二叉树上下翻转，并返回新的根节点。

你可以按下面的步骤翻转一棵二叉树：

1. 原来的左子节点变成新的根节点
2. 原来的根节点变成新的右子节点
3. 原来的右子节点变成新的左子节点

上面的步骤逐层进行。题目数据保证每个右节点都有一个同级节点（即共享同一父节点的左节点）且不存在子节点。

 

示例 1：

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

示例 2：

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

示例 3：

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

 

提示：

• 树中节点数目在范围 [0, 10] 内
• 1 <= Node.val <= 10
• 树中的每个右节点都有一个同级节点（即共享同一父节点的左节点）
• 树中的每个右节点都没有子节点

方法一：递归 · Go 实现

思考

题目保证右孩子要么不存在，要么是叶子且必有左兄弟，树呈「左链 + 右叶子」。 $n\le 10$。翻转后原最左叶子成为新根，原根变成它的右孩子，原右孩子变成左孩子。沿左链递归到底，回溯时按这个规则改指针并清空原根的左右，返回新根。

若根节点为空，或者根节点左子树为空，直接返回根节点。

递归处理左子树，返回的根节点 newRoot，也就是二叉树上下翻转后的根节点。

然后处理根节点 root，根节点变成左子节点的右子节点，而根节点的右子节点变成左子节点的左子节点。

接着将根节点 root 的左右子节点置为空，最后返回 newRoot 即可。

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

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func upsideDownBinaryTree(root *TreeNode) *TreeNode {
	if root == nil || root.Left == nil {
		return root
	}
	newRoot := upsideDownBinaryTree(root.Left)
	root.Left.Right = root
	root.Left.Left = root.Right
	root.Left = nil
	root.Right = nil
	return newRoot
}

力扣原题 · Doocs 题解来源

199. 二叉树的右视图

中等2 种解法

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

题目、示例与约束

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

 

示例 1：

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

输出：[1,3,4]

解释：

示例 2：

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

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

解释：

示例 3：

输入：root = [1,null,3]

输出：[1,3]

示例 4：

输入：root = []

输出：[]

 

提示:

• 二叉树的节点个数的范围是 [0,100]
• -100 <= Node.val <= 100 

方法一：BFS · Go 实现

思考

从右侧看，每层只看到最右边的节点。 $n\le 100$。层序时先把右孩子入队，则队头就是该层最右节点，记下后即可扫完本层。不必事后再取每层末尾。

我们可以使用广度优先搜索，定义一个队列 $\mathit{\text{q}}$，将根节点放入队列中。每次从队列中取出当前层的所有节点，对于当前节点，我们先判断右子树是否存在，若存在则将右子树放入队列中；再判断左子树是否存在，若存在则将左子树放入队列中。这样每次取出队列中的第一个节点即为该层的右视图节点。

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

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

方法二：DFS · Go 实现

思考

方法一用队列。先递归右子树再左子树，并带上深度：某深度第一次到达时记下的就是该层最右节点，空间随高度而不是宽度。

使用 DFS 深度优先遍历二叉树，每次先遍历右子树，再遍历左子树，这样每层第一个遍历到的节点即为该层的右视图节点。

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

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

力扣原题 · Doocs 题解来源

222. 完全二叉树的节点个数

中等2 种解法

标签：位运算、树、二分查找、二叉树

题目、示例与约束

给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层（从第 0 层开始），则该层包含 1~ 2h 个节点。

 

示例 1：

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

示例 2：

输入：root = []
输出：0

示例 3：

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

 

提示：

• 树中节点的数目范围是[0, 5 * 104]
• 0 <= Node.val <= 5 * 104
• 题目数据保证输入的树是 完全二叉树

 

进阶：遍历树来统计节点是一种时间复杂度为 O(n) 的简单解决方案。你可以设计一个更快的算法吗？

方法一：递归 · Go 实现

思考

完全二叉树仍可用普通递归统计左右子树规模。结点总数为 $1$ 加上两棵子树的结点数，遍历每个结点一次即可。

递归遍历整棵树，统计结点个数。

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

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

方法二：二分查找 · Go 实现

思考

方法一未利用“最后一层靠左填满”的结构，仍是线性扫描。左右子树高度相等则左子树为满二叉树，结点数可直接写成 $2^{left}$，只需递归右子树；否则右子树为满，递归左子树。

每次沿最左链求高为 $O(\log n)$，递归层数亦为 $O(\log n)$，总时间为 $O({\log }^{2}n)$。

对于此题，我们还可以利用完全二叉树的特点，设计一个更快的算法。

完全二叉树的特点：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。需要注意的是，满二叉树肯定是完全二叉树，而完全二叉树不一定是满二叉树。

若满二叉树的层数为 $h$，则总结点数为 $2^h-1$。

我们可以先对 $root$ 的左右子树进行高度统计，分别记为 $left$ 和 $right$。

1. 若 $left=right$，说明左子树是一颗满二叉树，那么左子树的结点总数为 $2^{left}-1$，加上 $root$ 结点，就是 $2^{left}$，然后递归统计右子树即可。
2. 若 $left>right$，说明右子树是一个满二叉树，那么右子树的结点总数为 $2^{right}-1$，加上 $root$ 结点，就是 $2^{right}$，然后递归统计左子树即可。

时间复杂度 $O({\log }^{2}n)$。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func countNodes(root *TreeNode) int {
	if root == nil {
		return 0
	}
	left, right := depth(root.Left), depth(root.Right)
	if left == right {
		return (1 << left) + countNodes(root.Right)
	}
	return (1 << right) + countNodes(root.Left)
}

func depth(root *TreeNode) (d int) {
	for ; root != nil; root = root.Left {
		d++
	}
	return
}

力扣原题 · Doocs 题解来源

226. 翻转二叉树

简单1 种解法

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

题目、示例与约束

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

 

示例 1：

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

示例 2：

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

示例 3：

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

 

提示：

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

方法一：递归 · Go 实现

思考

翻转整棵树即交换每个结点的左右孩子，并对其子树做同样操作。树规模允许一次递归遍历。

先递归翻转左右子树，再交换两棵子树的根指针。

我们首先判断 $\mathit{\text{root}}$ 是否为空，若为空则直接返回 $\text{null}$。然后递归地对树的左右子树进行翻转，将翻转后的右子树作为新的左子树，将翻转后的左子树作为新的右子树，返回 $\mathit{\text{root}}$。

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

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

力扣原题 · Doocs 题解来源