Posted by 微博@Yangsc_o
原创文章，版权声明：自由转载-非商用-非衍生-保持署名 | Creative Commons BY-NC-ND 3.0

95. 不同的二叉搜索树 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

解析：

先看如何构造一颗平衡二叉搜索树

func generateTrees(n int) *TreeNode {

	return helper(1, n)

}

func helper(start, end int) *TreeNode {

	if start > end {

		return nil

	}

        // 平衡二叉搜索树

	i := (start + end) / 2

	root := &TreeNode{Val: i}

	root.Left = helper(start, i-1)

	root.Right = helper(i+1, end)

	return root

}

根据题目的意思，需要在上面的代码中，在选择根结点的时候，遍历跟节点所有的可能；

即：i := (start + end) / 2 的可能值为从start到end

	for  i := start; i <= end; i++{

		root := &TreeNode{Val: i};

	}

当找到root节点时，问题就变为如何构建root的左右子树。

固定左孩子，遍历右孩子

	for _, leftNode := range left {

		for _, rightNode := range right {

			root := &TreeNode{Val: i}

			root.Left = leftNode

			root.Right = rightNode

		}

	}

/**

 * Definition for a binary tree node.

 * type TreeNode struct {

 *     Val int

 *     Left *TreeNode

 *     Right *TreeNode

 * }

 */

func generateTrees(n int) []*TreeNode {

    return helper(1,n)

}

func helper(start,end int) []*TreeNode {

    res := make([]*TreeNode, 0)

    if start > end {

        res = append(res, nil)

        return res

    }

    // 1.穷举所有以 i 为 root 节点的所有可能

    for i:= start; i <= end;i ++ {

        left := helper(start,i - 1)

        right := helper(i + 1 ,end)

        // 2.递归所有 root 节点的左右子树

        for _, leftNode := range left {

            for _, rightNode := range right {

                 // 3.给 root 节点穷举所有左右子树的组合

                root := &TreeNode{Val: i}

                root.Left = leftNode

                root.Right = rightNode

                res = append(res, root)

            }

        }

    }

    return res

}

参考

Krains's Blog-不同的二叉搜索树 II

你的鼓励也是我创作的动力

打赏地址

巴特西

[leetcode]95.不同的二叉搜索树

95. 不同的二叉搜索树 II

参考

Krains's Blog-不同的二叉搜索树 II

你的鼓励也是我创作的动力

最新文章

热门文章