LeetCode_BinaryTree_95. Unique Binary Search Trees II 不同的二叉搜尋樹 II【遞歸，搜尋樹】【java】【中等】

目錄

​​一，題目描述​​

​​英文描述​​

​​中文描述​​

​​示例與說明​​

​​二，解題思路​​

​​三，AC代碼​​

​​Java​​

​​四，解題過程​​

​​第一博​​

​​第二搏​​

一，題目描述

英文描述

Given an integer n, return all the structurally unique BST's (binary search trees), which has exactly n nodes of unique values from 1 to n. Return the answer in any order.

中文描述

給你一個整數 ​

​n​

​​ ，請你生成并傳回所有由 ​

​n​

​​ 個節點組成且節點值從 ​

​1​

​​ 到 ​

​n​

​ 互不相同的不同 二叉搜尋樹 。可以按 任意順序 傳回答案。

示例與說明

​

​1 <= n <= 8​

​

來源：力扣（LeetCode）

連結：​​​力扣​​ 著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

二，解題思路

參考​​@力扣官方題解【不同的二叉搜尋樹 II】​​

由于線索樹節點的取值是1-n，很大程度上簡化了該題的難度。直接上代碼

三，AC代碼

Java

class Solution {
    public List<TreeNode> build (int start, int end) {
        List<TreeNode> allTrees = new ArrayList<>();
        if (start > end) {
            allTrees.add(null);// !!!這裡不添加null，直接傳回allTrees會報錯。。。
            return allTrees;
        }
        for (int i = start; i <= end; i++) {
            List<TreeNode> leftTrees = build(start, i - 1);// 獲得所有的左子樹節點
            List<TreeNode> rightTrees = build(i + 1, end);// 獲得所有的右子樹節點
            for (TreeNode left : leftTrees) {
                for (TreeNode right : rightTrees) {
                    TreeNode head = new TreeNode(i);// 建構搜尋樹
                    head.left = left;
                    head.right = right;
                    allTrees.add(head);
                }
            }
        }
        return allTrees;
    }
    public List<TreeNode> generateTrees(int n) {
        if (n == 0) return null;
        List<TreeNode> ans = build(1, n);
        return ans;
    }
}      

四，解題過程

第一博

第一眼看上去就感覺要用遞歸，但是具體怎麼建構搜尋樹沒有頭緒。。。

第二搏

本來以為遞歸自己已經掌握的很熟練了，這道題狠狠的打了我的臉。。。

遞歸的核心思想就是将原來的問題抽象成子問題的集合。

針對這一題來說。雖然第一眼就知道要用遞歸來實作，但卻陷入了太多的細節之中，比如

• 如何判斷哪個數字被周遊過、
• 怎樣在建構線索樹的同時記錄樹的根節點、
• 怎樣定位下一個要周遊的數字、
• 生成的線索樹如何避免重複等等

這樣一來，編寫的程式就顯得極為複雜。

其實上面思路産生的原因就是忘記了遞歸最核心的功能。

假如這個函數能産生正确的線索樹，那麼目前節點的左右子樹不就出來了嗎？需要做的僅僅是将他們拼接到目前節點的左右子樹部分。

剩下的問題就是如何确定目前節點的值，以及遞歸方法需要的參數。

• 确定目前節點的值：可能的取值範圍内逐個周遊；
• 遞歸方法需要的參數：可能的取值範圍，即左右邊界；