目录

94. 二叉树的中序遍历 Binary Tree Inorder Traversal  🌟

95. 不同的二叉搜索树 II Unique Binary Search Trees II  🌟🌟

96. 不同的二叉搜索树 Unique Binary Search Trees  🌟🌟

🌟 每日一练刷题专栏 🌟

Golang每日一练 专栏

Python每日一练 专栏

C/C++每日一练 专栏

Java每日一练 专栏

二叉树专题（1）

94. 二叉树的中序遍历 Binary Tree Inorder Traversal

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

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

代码1： 递归法

type TreeNode struct {Val intLeft *TreeNodeRight *TreeNode
}func inorderTraversal(root *TreeNode) []int {var res []intinorder(root, &res)return res
}func inorder(root *TreeNode, res *[]int) {if root == nil {return}inorder(root.Left, res)*res = append(*res, root.Val)inorder(root.Right, res)
}

代码2： 迭代法

type TreeNode struct {Val intLeft *TreeNodeRight *TreeNode
}func inorderTraversal(root *TreeNode) []int {var res []intstack := []*TreeNode{}cur := rootfor cur != nil || len(stack) > 0 {for cur != nil {stack = append(stack, cur)cur = cur.Left}cur = stack[len(stack)-1]stack = stack[:len(stack)-1]res = append(res, cur.Val)cur = cur.Right}return res
}

95. 不同的二叉搜索树 II Unique Binary Search Trees II

给你一个整数 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

代码1： 递归法

type TreeNode struct {Val intLeft *TreeNodeRight *TreeNode
}func generateTrees(n int) []*TreeNode {if n == 0 {return []*TreeNode{}}return generate(1, n)
}func generate(start, end int) []*TreeNode {if start > end {return []*TreeNode{nil}}var res []*TreeNodefor i := start; i <= end; i++ {left := generate(start, i-1)right := generate(i+1, end)for _, l := range left {for _, r := range right {res = append(res, &TreeNode{i, l, r})}}}return res
}

代码2： 动态规划

type TreeNode struct {Val intLeft *TreeNodeRight *TreeNode
}func generateTrees(n int) []*TreeNode {if n == 0 {return []*TreeNode{}}dp := make([][]*TreeNode, n+1)dp[0] = []*TreeNode{nil}for i := 1; i <= n; i++ {var res []*TreeNodefor j := 1; j <= i; j++ {for _, l := range dp[j-1] {for _, r := range dp[i-j] {res = append(res, &TreeNode{j, l, r})}}}dp[i] = res}return dp[n]
}

96. 不同的二叉搜索树 Unique Binary Search Trees

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

示例 1：

输入：n = 3
输出：5

示例 2：

输入：n = 1
输出：1

提示：

• 1 <= n <= 19

代码1： 动态规划

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

代码2： 组合

卡特兰数Cn满足以下递推式： C0 = 1, Cn+1 = 2(2n+1)/(n+2) * Cn

func numTrees(n int) int {c := 1for i := 0; i < n; i++ {c = c * 2 * (2*i+1) / (i+2)}return c
}

🌟 每日一练刷题专栏 🌟

✨ 持续，努力奋斗做强刷题搬运工！

👍 点赞，你的认可是我坚持的动力！ 

🌟 收藏，你的青睐是我努力的方向！ 

✎ 评论，你的意见是我进步的财富！  

☸ 主页：https://hannyang.blog.csdn.net/ 

	Golang每日一练 专栏
	Python每日一练 专栏
	C/C++每日一练 专栏
	Java每日一练 专栏