当前位置:   article > 正文

leetcode 894. 所有可能的完整二叉树_leetcode 894 二叉树

leetcode 894 二叉树

题目:

完整二叉树是一类二叉树,其中每个结点恰好有 0 或 2 个子结点。

返回包含 N 个结点的所有可能完整二叉树的列表。 答案的每个元素都是一个可能树的根结点。

答案中每个树的每个结点必须有 node.val=0

你可以按任何顺序返回树的最终列表。

 

示例:

输入:7
输出:[[0,0,0,null,null,0,0,null,null,0,0],[0,0,0,null,null,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,null,null,null,null,0,0],[0,0,0,0,0,null,null,0,0]]
解释:

 

提示:

  • 1 <= N <= 20

思路:

中等题,其实思路不难,对于我这种手残选手而言,难的是coding。一看就是递归解决,并且一个端点只允许两种情况,无节点或者两个节点。但是其返回值是头结点,用简单的递归是返回不了头结点的,因为递归总是从上而下的,递归到最后就是子节点的。这题需要在返回的时候声明一个节点作为头结点root,然后左右递归的子返回值作为其子节点,我们就可以返回这个root了。

注意点:

递归的返回值,需要自行声明一个新的节点作为这个子树的头结点。

代码:

  1. vector<TreeNode*> allPossibleFBT(int N) {
  2. cout<<N<<endl;
  3. vector<TreeNode*> ve;
  4. if(N==0)return ve;
  5. if(N==1){
  6. TreeNode* ans = new TreeNode(0);
  7. ve.push_back(ans);
  8. return ve;
  9. }
  10. N = N-1;
  11. for(int i=1;i<=N;i+=2){
  12. vector<TreeNode*> L = allPossibleFBT(i);
  13. vector<TreeNode*> R = allPossibleFBT(N-i);
  14. for(TreeNode* i : L){
  15. for(TreeNode* j : R){
  16. TreeNode* root = new TreeNode(0);
  17. root->left = i;
  18. root->right = j;
  19. ve.push_back(root);
  20. }
  21. }
  22. }
  23. return ve;
  24. }

 

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/天景科技苑/article/detail/783431
推荐阅读
相关标签
  

闽ICP备14008679号