当前位置:网站首页>Leetcode-096-different binary search trees

Leetcode-096-different binary search trees

2021-11-25 17:50:00 Lion, tiger and leopard

Title Description : Give you an integer n , Seek just by n Composed of nodes with node values from 1 To n Different from each other Binary search tree How many kinds? ? Returns the number of binary search trees satisfying the meaning of the question .

Binary search tree (Binary Search Tree): Also called binary sorting tree , It could be an empty tree , Or a binary tree that has the following properties : If its left subtree is not empty , Then the value of all nodes in the left subtree is less than the value of its root node ; If its right subtree is not empty , Then the value of all nodes in the right subtree is greater than the value of its root node ; Its left 、 The right subtree is also a binary sort tree .

Please refer to LeetCode Official website .

source : Power button (LeetCode)
link :https://leetcode-cn.com/problems/unique-binary-search-trees/
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Solution 1 : Recursive method
  • First , When n by 0 When , The result is an empty tree , Go straight back to the empty list.
  • When n Greater than 0 When , Use the recursive method to obtain the left and right subtrees respectively , The recursive process is as follows :
    • All nodes can be used as root nodes , That is, traversing from 1 To n All values of as the root node , The current root node is i;
    • then i All the values on the left call the method recursively as i The left subtree ;
    • i All the values on the right call the method recursively as i The right subtree ;
    • Finally, put the root node i And the corresponding left and right subtrees to form a tree , Put it in the result set .
  • Last , Of the result set size Value is the number of qualified binary search trees .

explain : The method refers to LeetCode-095- Different binary search trees II, However, the submission timed out .

Solution 1 : law

Find the law , When the integer is n when , The result of binary search is the sum of all the possible results in the front .

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

public class LeetCode_096 {
    /**
     *  recursive : The method timed out while running 
     *
     * @param n
     * @return
     */
    public static int numTrees(int n) {
        //  When n by 0 When , It's an empty tree 
        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++) {
            //  All possible left subtree sets 
            List<TreeNode> leftTrees = generateTrees(start, i - 1);

            //  All possible right subtree sets 
            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));
    }
}

【 Daily message 】 Youth is capital , But it's not worth the money if you don't work hard .

版权声明
本文为[Lion, tiger and leopard]所创,转载请带上原文链接,感谢
https://chowdera.com/2021/11/20211109093107145i.html

随机推荐