二叉搜索树与双向链表

た 入场券 2023-02-17 12:25 37阅读 0赞

输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。

遇树不决就递归

  1. /*
  2. struct TreeNode {
  3. int val;
  4. struct TreeNode *left;
  5. struct TreeNode *right;
  6. TreeNode(int x) :
  7. val(x), left(NULL), right(NULL) {
  8. }
  9. };*/
  10. class Solution {
  11. public:
  12. TreeNode* Convert(TreeNode* pRootOfTree)
  13. {
  14. if(pRootOfTree == NULL) return NULL;
  15. if(pRootOfTree->left == NULL && pRootOfTree->right == NULL) return pRootOfTree;
  16. if(pRootOfTree->left == NULL) {
  17. TreeNode * temp = Convert(pRootOfTree->right);
  18. pRootOfTree->right = temp;
  19. temp->left = pRootOfTree;
  20. return pRootOfTree;}
  21. if(pRootOfTree->right == NULL) {
  22. TreeNode * temp = Convert(pRootOfTree->left);
  23. TreeNode * tmp = temp;
  24. while(temp->right) {
  25. temp = temp->right;
  26. }
  27. temp->right = pRootOfTree;
  28. pRootOfTree->left = temp;
  29. return tmp;
  30. }
  31. TreeNode * temp = Convert(pRootOfTree->left);
  32. TreeNode * tmp = temp;
  33. while(temp->right) {
  34. temp = temp->right;
  35. }
  36. temp->right = pRootOfTree;
  37. pRootOfTree->left = temp;
  38. temp = Convert(pRootOfTree->right);
  39. pRootOfTree->right = temp;
  40. temp->left = pRootOfTree;
  41. return tmp;
  42. }
  43. };

发表评论

表情:
评论列表 (有 0 条评论,37人围观)

还没有评论,来说两句吧...

相关阅读

    相关 搜索双向

    \\题目描述 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。 思路 关于树的深度搜索操作,一般都

    相关 搜索双向

    [二叉搜索树与双向链表][Link 1] 题目描述 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向

    相关 搜索双向

    时间限制:1秒 空间限制:32768K 热度指数:210251 算法知识视频讲解 题目描述 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建