LeetCode 95
这道题是和不同的二叉树的个数问题相关的(Unique Binary Search Trees),不同之处在于问题一中只要求统计个数,而问题二中需要构造出所有的二叉树。
问题一用DP的方法是很容易实现的,是因为二叉树固定数字生成的二叉树是固定的,一个二叉树的种类由它可能的左子树和右子树数目决定的,所以DP轻松解决。
问题二我陷入了用DP的思路,后来事实证明DP也是可以完成的。但是我看到的更好的解法是用自上而下递归的策略。调用helper(1,n)
完成。
vector<TreeNode*> helper(int start, int end) {
vector<TreeNode *> results;
if (start>end)
{
results.push_back(NULL);
return results;
}
for (int k = start; k <= end; k++)
{
vector<TreeNode *> left = helper(start, k - 1);
vector<TreeNode *> right = helper(k + 1, end);
for (int i = 0; i<left.size(); i++)
{
for (int j = 0; j<right.size(); j++)
{
TreeNode * root = new TreeNode(k);
root->left = left[i];
root->right = right[j];
results.push_back(root);
}
}
}
return results;
}
同时也说明一下另外一种解法。我们对于某一次生成有如下考虑
- 新的根只需要把之前的根作为自己的左子树。
- 新的节点不作为根加入之前的树,由于它是最大的肯定是一路向右。所以可以遍历之前的树,对于每一棵树,从根的右节点逐步下移,截断处剩下的部分作为新节点的左子树,直到最右侧的叶子节点为止。
LeetCode 99
题意描述:一个二叉树中的两个节点由于某些错误被交换了,找出他们并恢复二叉树。(空间复杂度上O(n)很容易,但是O(1)是不容易实现的)
这道题一开始我的思路是分别搜索一个根的左子树和右子树,比较根和左右节点关系是否正确,后来又考虑了交换的节点在树的一侧的情况和不在同一侧的情况,最后没有AC掉这道题。
这道题正确的思路应该考虑二叉树的性质,二叉树在中序遍历的时候(in order)数据的输出是从小到大的,
那么采用先序遍历二叉树的方式,就相当于顺序遍历数组发现被交换的两个数。