二叉树专题（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： 递归法
package main import ( "fmt" ) const null = -1 << 31 type TreeNode struct { Val int Left *TreeNode Right *TreeNode } func inorderTraversal(root *TreeNode) []int { var res []int inorder(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) } func buildTree(nums []int) *TreeNode { if len(nums) == 0 { return nil } root := &TreeNode{Val: nums[0]} Queue := []*TreeNode{root} idx := 1 for idx < len(nums) { node := Queue[0] Queue = Queue[1:] if nums[idx] != null { node.Left = &TreeNode{Val: nums[idx]} Queue = append(Queue, node.Left) } idx++ if idx < len(nums) && nums[idx] != null { node.Right = &TreeNode{Val: nums[idx]} Queue = append(Queue, node.Right) } idx++ } return root } func ArrayToString(arr []int) string { res := "[" for i := 0; i < len(arr); i++ { res += fmt.Sprint(arr[i]) if i != len(arr)-1 { res += "," } } return res + "]" } func main() { nums := []int{1, null, 2, 3} root := buildTree(nums) fmt.Println(ArrayToString(inorderTraversal(root))) nums = []int{3, 9, 20, null, null, 15, 7} root = buildTree(nums) fmt.Println(ArrayToString(inorderTraversal(root))) }
代码2： 迭代法
package main import ( "fmt" ) const null = -1 << 31 type TreeNode struct { Val int Left *TreeNode Right *TreeNode } func inorderTraversal(root *TreeNode) []int { var res []int stack := []*TreeNode{} cur := root for 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 } func buildTree(nums []int) *TreeNode { if len(nums) == 0 { return nil } root := &TreeNode{Val: nums[0]} Queue := []*TreeNode{root} idx := 1 for idx < len(nums) { node := Queue[0] Queue = Queue[1:] if nums[idx] != null { node.Left = &TreeNode{Val: nums[idx]} Queue = append(Queue, node.Left) } idx++ if idx < len(nums) && nums[idx] != null { node.Right = &TreeNode{Val: nums[idx]} Queue = append(Queue, node.Right) } idx++ } return root } func ArrayToString(arr []int) string { res := "[" for i := 0; i < len(arr); i++ { res += fmt.Sprint(arr[i]) if i != len(arr)-1 { res += "," } } return res + "]" } func main() { nums := []int{1, null, 2, 3} root := buildTree(nums) fmt.Println(ArrayToString(inorderTraversal(root))) nums = []int{3, 9, 20, null, null, 15, 7} root = buildTree(nums) fmt.Println(ArrayToString(inorderTraversal(root))) }
输出：
[1,3,2]
[9,3,15,20,7]
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 int Left *TreeNode Right *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 []*TreeNode for 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 int Left *TreeNode Right *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 []*TreeNode for 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] = 1 for 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 := 1 for i := 0; i < n; i++ { c = c * 2 * (2*i+1) / (i+2) } return c }
