[剑指Offer]二叉搜索树与双向链表 -电脑资料

电脑资料 时间:2019-01-01 我要投稿
【www.unjs.com - 电脑资料】

   

题目描述

    输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表,

[剑指Offer]二叉搜索树与双向链表

。要求不能创建任何新的结点,只能调整树中结点指针的指向。

算法描述

    使用递归,分别去将当前节点的左右子树变成双向链表,然后获取左边链表的最后一个元素,当前元素的左指针指向它,它的右指针指向当前元素;右边链表的第一个元素,它的左指针指向当前元素,当前元素的右指针指向它;然后从当前元素开始,不断从左边找,找到第一个元素,返回此元素的指针。

    总结

    对这种涉及到二叉树的题目,可以使用测试驱动开始,先写测试用例,然后再编码。

代码实现

<code class="hljs" lasso="">#include<iostream>using std::cout;using std::cin;using std::endl;struct TreeNode {     int val;     struct TreeNode *left;     struct TreeNode *right;     TreeNode(int x) :       val(x), left(NULL), right(NULL) {     }};class Solution {public:    TreeNode* Convert(TreeNode* pRootOfTree)    {          TreeNode* p = pRootOfTree;          TreeNode* pl;          TreeNode* pr;          if( p != NULL ) {               pl = Convert(p->left);               pr = Convert(p->right);               p->right= pr;               if(pr){                    pr->left = p;               }               while(pl&&pl->right){                    pl = pl->right;               }               if(pl)                    pl->right= p;               p->left= pl;               while(p->left){                    p = p->left;               }          }          return p;    }};int main(){     TreeNode* p1 = new TreeNode(1);     TreeNode* p2 = new TreeNode(2);     TreeNode* p3 = new TreeNode(3);     TreeNode* p4 = new TreeNode(4);     TreeNode* p5 = new TreeNode(5);     TreeNode* p6 = new TreeNode(6);     TreeNode* p7 = new TreeNode(7);     p4->left = p2;     p4->right= p6;     p2->left = p1;     p2->right= p3;     p6->left= p5;     p6->right= p7;     Solution s;     TreeNode* p = s.Convert(p4);     while(p->right){      cout<<p->val<< ;      p = p->right;     }     cout<<p->val<< ;     cout<<;     while(p->left){      cout<<p->val<< ;      p = p->left;     }     cout<<p->val<< ;}</p-></p-></p-></p-></iostream></code>

最新文章