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

题目链接 : https://leetcode-cn.com/problems/unique-binary-search-trees-ii/

题目描述:

给定一个整数 n，生成所有由 1 ... n 为节点所组成的二叉搜索树。

示例:

输入: 3

输出:

[

  [1,null,3,2],

  [3,2,null,1],

  [3,1,null,null,2],

  [2,1,3],

  [1,null,2,null,3]

]

解释:

以上的输出对应以下 5 种不同结构的二叉搜索树：

   1         3     3      2      1

    \       /     /      / \      \

     3     2     1      1   3      2

    /     /       \                 \

   2     1         2                 3

思路:

二叉搜索树, 一节点大于左子树节点, 小于右子树节点

所以我们节点是从1到n,当一个节点为val那么它的左边是< val,右边是>val,

我们用递归解决!

代码:

# Definition for a binary tree node.

# class TreeNode:

#     def __init__(self, x):

#         self.val = x

#         self.left = None

#         self.right = None

import functools

class Solution:

    def generateTrees(self, n: int) -> List[TreeNode]:

        if n == 0: return []

        @functools.lru_cache(None)

        def helper(start, end):

            res = []

            if start > end:

                res.append(None)

            for val in range(start, end + 1):

                for left in helper(start, val - 1):

                    for right in helper(val + 1, end):

                        root = TreeNode(val)

                        root.left = left

                        root.right = right

                        res.append(root)

            return res

        return helper(1, n)

java

/**

 * Definition for a binary tree node.

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode(int x) { val = x; }

 * }

 */

class Solution {

    public List<TreeNode> generateTrees(int n) {

        if (n == 0) return new ArrayList<>();

        return helper(1, n);

    }

    private List<TreeNode> helper(int start, int end) {

        List<TreeNode> res = new ArrayList<>();

        if (start > end) {

            res.add(null);

            return res;

        }

        for (int val = start; val <= end; val++) {

            List<TreeNode> left = helper(start, val - 1);

            List<TreeNode> right = helper(val + 1, end);

            for (TreeNode l : left) {

                for (TreeNode r : right) {

                    TreeNode root = new TreeNode(val);

                    root.left = l;

                    root.right = r;

                    res.add(root);

                }

            }

        }

        return res;

    }

}

巴特西

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

题目描述:

示例:

思路:

代码:

最新文章

热门文章