乐趣区

关于java:LeetCode096不同的二叉搜索树

jiezi

不同的二叉搜寻树

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

二叉搜寻树（Binary Search Tree）： 又称二叉排序树，它或者是一棵空树，或者是具备下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也别离为二叉排序树。

示例阐明请见 LeetCode 官网。

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl…
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

解法一：递归法
  • 首先，当 n 为 0 的时候，后果是一棵空树，间接返回空的 list。

  • 当 n 大于 0 的时候，应用递归的办法来别离获取左右子树，递归过程如下：

    • 所有节点都能够作为根节点，也就是遍历从 1 到 n 的所有值作为根节点，以后根节点为 i；
    • 而后 i 右边的所有的值递归调用办法作为 i 的左子树；
    • i 左边的所有的值递归调用办法作为 i 的右子树；
    • 最初把根节点 i 和相应的左右子树拼成一棵树，放到后果集中。
  • 最初，返回后果集的 size 值即为符合条件的二叉搜寻树的种数。

阐明： 该办法参照的 LeetCode-095- 不同的二叉搜寻树 II，不过在提交的时候超时了。

解法一：法则

找法则可知，当整数为 n 时，二叉搜寻数的后果是后面所有可能的后果之和。

import com.kaesar.leetcode.TreeNode;
import java.util.ArrayList;
import java.util.List;

public class LeetCode_096 {
    /**
     * 递归：该办法运行时超时了
     *
     * @param n
     * @return
     */
    public static int numTrees(int n) {
        // 当 n 为 0 的时候，是一棵空树
        if (n == 0) {return 1;}
        return generateTrees(1, n).size();}

    private static List<TreeNode> generateTrees(int start, int end) {List<TreeNode> allTrees = new ArrayList<>();
        if (start > end) {allTrees.add(null);
            return allTrees;
        }
        for (int i = start; i <= end; i++) {
            // 所有可能的左子树汇合
            List<TreeNode> leftTrees = generateTrees(start, i - 1);

            // 所有可能的右子树汇合
            List<TreeNode> rightTrees = generateTrees(i + 1, end);

            for (TreeNode leftTree : leftTrees) {for (TreeNode rightTree : rightTrees) {TreeNode root = new TreeNode(i);
                    root.left = leftTree;
                    root.right = rightTree;
                    allTrees.add(root);
                }
            }
        }
        return allTrees;
    }
    
    public static int numTrees2(int n) {int[] result = new int[n + 1];
        result[0] = 1;
        result[1] = 1;
        for (int i = 2; i <= n; i++) {for (int j = 1; j <= i; j++) {result[i] += result[j - 1] * result[i - j];
            }
        }
        return result[n];
    }

    public static void main(String[] args) {System.out.println(numTrees(3));
        System.out.println(numTrees2(3));
    }
}

【每日寄语】 年老是成本，但不致力就不值钱。

退出移动版