首页 > 代码库 > 【LeetCode】Unique Binary Search Trees II 不同的二叉查找树II

【LeetCode】Unique Binary Search Trees II 不同的二叉查找树II

  今早起来做 LeetCode,结果被这道题卡了将近1个半小时,忍着没有去搜答案,最后还是被我想出来了,而且直接一次AC,哈哈!现在在这里记录一下解题思路。

 


 

 

原题:

Given n, generate all structurally unique BST‘s (binary search trees) that store values 1...n.

For example,
Given n = 3, your program should return all 5 unique BST‘s shown below.

     1         3     3      2      1      \       /     /      / \             3     2     1      1   3      2      /     /       \                      2     1         2                 3
OJ‘s Binary Tree Serialization:

The serialization of a binary tree follows a level order traversal, where ‘#‘ signifies a path terminator where no node exists below.

Here‘s an example:

     1    /    2   3      /     4             5
The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".

 

解释:

对给定的数字 n生成所有储存了数字 1 至 n 的结构不同的 BST‘s (二叉查找树)。

举个栗子 ⊙o⊙,
假如给定的 n = 3,你的程序应该返回如下图所示的5个不同的二叉查找树。

     1         3     3      2      1      \       /     /      / \             3     2     1      1   3      2      /     /       \                      2     1         2                 3
OJ‘s 二叉树的序列化:

二叉树的序列化遵循水平阶遍历,“#”表示没有节点存在。

这儿有一个栗子 ⊙o⊙ :

     1    /    2   3      /     4             5
上图的二叉树序列化后的结果为“{1,2,3,#,#,4,#,#,5}”。

 

思路:

这道题是 Unique Binary Search Trees 的升级版,解决方法同样是动态规划。

在做 Unique Binary Search Trees 这道题时,我们用一个数组保存 1 至 n-1 对应的不同二叉树的个数 X1、X2、X3、... Xn-1

则 n 对应的不同二叉树个数Xn = Xn-1 + X1*Xn-2 + X2*Xn-3 + X3*Xn-4 + ... + Xn-2*X1 + Xn-1

   通过这个递推式,我们可以从 N = 1 开始递推,最后得到 N = n 时不同二叉查找树的个数。

 

与上述思路类似,我们可以通过深度优先搜索(递归)解决这道题。

因为二叉查找树满足父节点的值大于左子节点的值,小于右子节点的值,所以我们可以:

(1) 从 N=1 开始构建二叉查找树,则它的左子树节点数为 0,右子树节点数为 n-1;

(2) N=2 时,左子树节点数为 1,右子树节点数为 n-2;

……

(n) N=n 时,左子树节点数为 n-1,右子树节点数 0。

 

而在第(1)步中,右子树继续执行上述循环,子树的子树又执行这个循环,最终,我们可以将子树节点数减少到 1,而一个节点只有一种排列方式,所以此时可以毫不犹豫地将结果返回给上一级。然后包含有两个节点的二叉树排列方式又被返回给上一级。……

依此类推,我们最后可以得到所有不同结构的二叉查找树。

 

源码:

class Solution {public:    vector<TreeNode *> generateTrees(int n) {        return GenerateSubTree(1, n + 1);    }    vector<TreeNode*> GenerateSubTree(int l, int r) {        vector<TreeNode *> subTree;        if (l >= r) {            subTree.push_back(NULL);            return subTree;        }        if (l == r - 1) {            subTree.push_back(new TreeNode(l));            return subTree;        }        for (int i = l; i < r; ++i) {            vector<TreeNode *> leftSubTree = GenerateSubTree(l, i);            vector<TreeNode *> rightSubTree = GenerateSubTree(i + 1, r);            for (int m = 0; m < leftSubTree.size(); ++m) {                for (int n = 0; n < rightSubTree.size(); ++n) {                    TreeNode *root = new TreeNode(i);                    root->left = leftSubTree[m];                    root->right = rightSubTree[n];                    subTree.push_back(root);                }            }        }        return subTree;    }};

 

【LeetCode】Unique Binary Search Trees II 不同的二叉查找树II