【Leetcode】95~96 不同的二叉搜尋樹
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] ]
解釋:
以上的輸出對應以下 5 種不同結構的二叉搜尋樹:
13321 \/// \\ 321132 //\\ 2123
Leetcode 86
不同的二叉搜尋樹
給定一個整數 n,求以 1 ... n 為節點組成的二叉搜尋樹有多少種?
示例:
輸入: 3 輸出: 5 解釋: 給定 n = 3, 一共有 5 種不同結構的二叉搜尋樹: 13321 \/// \\ 321132 //\\ 2123
題解
搜尋二叉樹(BST)的定義
若它的左子樹不空,則左子樹上所有結點的值均小於它的根結點的值; 若它的右子樹不空,則右子樹上所有結點的值均大於它的根結點的值; 它的左、右子樹也分別為二叉排序樹。
給點一個數,去構造BST.
[1, 2, 3]
可以把這個數列做左子樹和右子樹的劃分:
[1] [2, 3]
[1, 2] [3]
[1, 2] [2, 3] 又可以做左子樹和右子樹的劃分.這是一個遞迴的過程.
把遞迴的結果構造起來,即可成為答案.
/** * 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 generateBST(1, n); } private List<TreeNode> generateBST(int left, int right) { List<TreeNode> res = new LinkedList<>(); if (left > right) { // 劃分不到的時候,這時候填null. res.add(null); return res; } for (int i = left; i <= right; i++) { List<TreeNode> leftTrees = generateBST(left, i - 1); List<TreeNode> rightTrees = generateBST(i + 1, right); for (TreeNode leftTree : leftTrees) { for (TreeNode rightTree : rightTrees) { // 注意,每個迴圈都要構造新的節點,不能在for 迴圈外面生成. TreeNode root = new TreeNode(i); root.left = leftTree; root.right = rightTree; res.add(root); } } } return res; } }
如果只需要數目,不需要生成具體的BST的話,只要能求出左子樹有幾種構造,右子樹有幾種構造,就可以最終確定.
而確定左子樹和右子樹的問題的時候,又可以劃分為子問題.
eg:
求 [1,2,3,4] 依賴於:
[1,2,3] [2,3,4]
又依賴於:
[1,2] [2,3] [3,4]的構造有幾種.
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++) { // 求解過程中,需要依賴於之前的解,狀態轉移方程為每一種劃分的左子樹和右子樹的構造方法乘積. res[i] += res[j - 1] * res[i - j]; } } return res[n]; } }