資訊專欄INFORMATION COLUMN
摘要：不同的二叉搜索樹輸入輸出解釋以上的輸出對(duì)應(yīng)以下種不同結(jié)構(gòu)的二叉搜索樹不同的二叉搜索樹給定一個(gè)整數(shù)，求以為節(jié)點(diǎn)組成的二叉搜索樹有多少種示例輸入輸出解釋給定一共有種不同結(jié)構(gòu)的二叉搜索樹題解搜索二叉樹的定義若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值
Leetcode 95 不同的二叉搜索樹 II
輸入: 3
輸出:
[ [1,null,3,2], [3,2,null,1], [3,1,null,null,2], [2,1,3], [1,null,2,null,3] ]
解釋:
以上的輸出對(duì)應(yīng)以下 5 種不同結(jié)構(gòu)的二叉搜索樹：
1 3 3 2 1
/ / /
3 2 1 1 3 2
/ /
2 1 2 3
Leetcode 86
不同的二叉搜索樹
給定一個(gè)整數(shù) n，求以 1 ... n 為節(jié)點(diǎn)組成的二叉搜索樹有多少種？
示例:
輸入: 3
輸出: 5
解釋:
給定 n = 3, 一共有 5 種不同結(jié)構(gòu)的二叉搜索樹:
1 3 3 2 1
/ / /
3 2 1 1 3 2
/ /
2 1 2 3
題解
搜索二叉樹(BST)的定義
若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值； 若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值； 它的左、右子樹也分別為二叉排序樹。
給點(diǎn)一個(gè)數(shù)，去構(gòu)造BST.
[1, 2, 3]
可以把這個(gè)數(shù)列做左子樹和右子樹的劃分:
[1] [2, 3]
[1, 2] [3]
[1, 2] [2, 3] 又可以做左子樹和右子樹的劃分.這是一個(gè)遞歸的過程.
把遞歸的結(jié)果構(gòu)造起來(lái),即可成為答案.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List generateTrees(int n) {
if (n == 0) return new ArrayList<>();
return generateBST(1, n);
}
private List generateBST(int left, int right) {
List res = new LinkedList<>();
if (left > right) {
// 劃分不到的時(shí)候,這時(shí)候填null.
res.add(null);
return res;
}
for (int i = left; i <= right; i++) {
List leftTrees = generateBST(left, i - 1);
List rightTrees = generateBST(i + 1, right);
for (TreeNode leftTree : leftTrees) {
for (TreeNode rightTree : rightTrees) {
// 注意,每個(gè)循環(huán)都要構(gòu)造新的節(jié)點(diǎn),不能在for 循環(huán)外面生成.
TreeNode root = new TreeNode(i);
root.left = leftTree;
root.right = rightTree;
res.add(root);
}
}
}
return res;
}
}
如果只需要數(shù)目,不需要生成具體的BST的話,只要能求出左子樹有幾種構(gòu)造,右子樹有幾種構(gòu)造,就可以最終確定.
而確定左子樹和右子樹的問題的時(shí)候,又可以劃分為子問題.
eg:
求 [1,2,3,4] 依賴于:
[1,2,3] [2,3,4]
又依賴于:
[1,2] [2,3] [3,4]的構(gòu)造有幾種.
class Solution {
public int numTrees(int n) {
int[] res = new int[n + 2];
res[0] = 1;
res[1] = 1;
// 沒有左子樹和右子樹
res[2] = 2;
for (int i = 3; i <= n; i++) {
// 從3求到n
for (int j = 1; j <= i; j++) {
// 求解過程中,需要依賴于之前的解,狀態(tài)轉(zhuǎn)移方程為每一種劃分的左子樹和右子樹的構(gòu)造方法乘積.
res[i] += res[j - 1] * res[i - j];
}
}
return res[n];
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/73295.html
摘要：也就是說(shuō)，有個(gè)節(jié)點(diǎn)的平衡二叉搜索樹，它的高度是。以搜索操作為例，如果二叉搜索樹的高度為，則時(shí)間復(fù)雜度為。二叉搜索樹的高度的確很重要。樹集合，中的或者中的，是由高度平衡的二叉搜索樹實(shí)現(xiàn)的。 ...
摘要：在這里我們使用數(shù)組中下標(biāo)為的位置來(lái)記錄個(gè)元素可以組成的平衡二叉樹的數(shù)量。在遞歸的過程中，我們找到以當(dāng)前節(jié)點(diǎn)作為根節(jié)點(diǎn)的所有平衡二叉樹，并將結(jié)果以形式返回上一級(jí)調(diào)用。 題目要求 Given n, how many structurally unique BSTs (binary search trees) that store values 1...n? For example, Gi...
摘要：有效二叉搜索樹定義如下節(jié)點(diǎn)的左子樹只包含小于當(dāng)前節(jié)點(diǎn)的數(shù)。所有左子樹和右子樹自身必須也是二叉搜索樹。而我們二叉搜索樹保證了左子樹的節(jié)點(diǎn)的值均小于根節(jié)點(diǎn)的值，根節(jié)點(diǎn)的值均小于右子樹的值，因此中序遍歷以后得到的序列一定是升序序列。 ...
摘要：注意這里的結(jié)構(gòu)和不同的二叉樹遍歷一樣，如果到空節(jié)點(diǎn)就返回，否則遞歸遍歷左節(jié)點(diǎn)和右節(jié)點(diǎn)。唯一不同是加入了和，所以要在遞歸之前先判斷是否符合和的條件。代碼如果該節(jié)點(diǎn)大于上限返回假如果該節(jié)點(diǎn)小于下限返回假遞歸判斷左子樹和右子樹 Validate Binary Search Tree Given a binary tree, determine if it is a valid binary...
摘要：小鹿題目驗(yàn)證二叉搜索樹給定一個(gè)二叉樹，判斷其是否是一個(gè)有效的二叉搜索樹。假設(shè)一個(gè)二叉搜索樹具有如下特征節(jié)點(diǎn)的左子樹只包含小于當(dāng)前節(jié)點(diǎn)的數(shù)。所有左子樹和右子樹自身必須也是二叉搜索樹。算法思路定義全局的變量，用來(lái)返回是否為二叉搜索樹。 Time：2019/4/24Title: Vaildata Binary Search TreeDifficulty: MediumAuthor: 小鹿 ...
閱讀 2986·2021-11-19 11:35
閱讀 2641·2021-11-02 14:40
閱讀 1477·2021-09-04 16:48
閱讀 3084·2019-08-30 15:55
閱讀 1846·2019-08-30 13:11
閱讀 2014·2019-08-29 11:12
閱讀 1160·2019-08-27 10:52
閱讀 3235·2019-08-26 18:36
