牛客—— JZ36 二叉搜索树与双向链表

• 审题： 将二叉搜索树，转为排序的双向链表。
• 思路： 首先排序，肯定是涉及中序遍历，因为中序遍历二叉搜索树，就是排序；其次二叉搜索树和双向链表的节点是类似的，只不过是结构不同罢了，所以中序按序取出节点，然后 再改变一下链接关系就好了；最后 难点就在于 如何改变链接关系。
• 画图：

必须记录 前一个节点，方便链接，对吧？这是必须的。

(1) 中序遍历我就不说了，现在肯定是从 4节点 开始记录为 cur，pre 默认给为 null

那么现在，4的左边已经链接好了，但是它的右边还没链接。

(2) 让 cur 的left 指向 pre ；pre的right 指向 cur再将 cur 赋值给 pre；cur 往上走来到 6节点。


这一步很关键，cur 的left 指向 pre 是将 cur当下节点的左边链接好；pre 的right 指向cur 是将上一个节点的右边链接好。所以 现在 6节点也是只链接好了左边，它的右边是下一步 才能完成的。

(3) 让 cur 的left 指向 pre ；pre的right 指向 cur；再将 cur 赋值给 pre；cur 往下走来到 8节点

cur 的 left 指向 pre ：

pre 的 right 指向 cur:

(4) 让 cur 的left 指向 pre ；pre的right 指向 cur；再将 cur 赋值给 pre；cur 往上走来到 10节点

cur 的left 指向 pre:

pre的right 指向 cur :

---

• 以上我画了一半，其实感觉也差不多了，咱们代码实现：

class Solution {
public:
    void inorder_treetolist(struct TreeNode* cur,struct TreeNode*&  pre) {
    if (cur == NULL)
        return ;

    inorder_treetolist(cur->left, pre);
    // 中序中，访问根节点
    cur->left = pre;
    if(pre)
    {
        pre->right = cur;
    }
    pre =cur;
    
    inorder_treetolist(cur->right,pre);
}

struct TreeNode* Convert(struct TreeNode* pRootOfTree ) {
    // write code here
    if (pRootOfTree == NULL)
        return NULL;

    struct TreeNode* prev = NULL;

    inorder_treetolist(pRootOfTree, prev);
    
    // 现在指向的 末尾，所以得向前走，找到头节点。
    struct TreeNode* head = pRootOfTree;
    while(head->left)
    {
        head = head->left;
    }

   return head;
   }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

• 看看结果：我是c++实现的，这点需要注意