首页 > 代码库 > 剑指offer之【二叉搜索树与双向链表】

剑指offer之【二叉搜索树与双向链表】

题目:

  二叉搜索树与双向链表

链接: 

  https://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5?tpId=13&tqId=11179&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

题目描述:

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

思路:

  对于一个二叉搜索树,当我们进行中序遍历的时候是按从小到大的顺序进行遍历。

  所以按照中序遍历的顺序,当我们遍历当前节点的时候,它的左子树已经转换成了一个排序的链表了,并且处在链表中的最后一个节点是当前值最大的节点,接着去遍历转换右子树。

代码:

  

 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         TreeNode * leftLastNode = nullptr;
15         ConvertNode(pRootOfTree, &leftLastNode);
16         TreeNode *head = leftLastNode;
17         while(head != nullptr && head->left != nullptr){
18             head = head->left;
19         }
20         return head;
21     }
22     void ConvertNode(TreeNode *root ,TreeNode **leftLastNode){
23         if(root == nullptr)
24               return;
25         TreeNode *node = root;        //当前节点
26         if(node->left != nullptr){
27             ConvertNode(node->left,leftLastNode);
28         }
29         node->left = *leftLastNode;
30         if(*leftLastNode != nullptr){
31             (*leftLastNode)->right = node;
32         }
33         *leftLastNode = node;
34         if(node->right != nullptr){
35             ConvertNode(node->right,leftLastNode);
36         }
37     }
38 };

 

剑指offer之【二叉搜索树与双向链表】