如何将二叉搜索树转化为一个有序的双向链表（原树上修改）

ゞ浴缸里的玫瑰 2023-09-28 18:33 9阅读 0赞

![8366da7309f74e79861396e5f7c549a9.png][]

注意事项：
    
    1.要求不能创建任何新的结点，只能调整树中结点指针的指向。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继
    2.返回链表中的第一个节点的指针
    3.函数返回的TreeNode，有左右指针，其实可以看成一个双向链表的数据结构
    4.你不用输出双向链表，程序会根据你的返回值自动打印输出

> 分析：

![903622fa13ad431ab6881838e42bf07c.png][]

![459daf412ea447ecb3517c27f81294c7.png][]

![073fda1d2b214c3bb9a0046347df7157.png][]

![4cb4f74c12554abbafa65d0474e2ce07.png][]

> 代码如下：

import java.util.*;
    public class Solution {
        TreeNode prev = null;
        public TreeNode createList(TreeNode root){
            if(root == null){
                return null;
            }
            createList(root.left);
            root.left = prev;
            if(prev != null){
                prev.right = root;
            }
            prev = root;
            createList(root.right);
            return root;//最后返回根结点
        }
        public TreeNode Convert(TreeNode pRootOfTree) {
            if(pRootOfTree == null){
                return null;
            }
            TreeNode head = createList(pRootOfTree);
            //需要遍历到链表的头节点
            while(head.left != null){
                head = head.left;
            }
            return head;
        }   
    }

--------------------

![44625f552272452fa5639d7b14c1c6e4.gif][]

[8366da7309f74e79861396e5f7c549a9.png]: https://img-blog.csdnimg.cn/8366da7309f74e79861396e5f7c549a9.png
[903622fa13ad431ab6881838e42bf07c.png]: https://img-blog.csdnimg.cn/903622fa13ad431ab6881838e42bf07c.png
[459daf412ea447ecb3517c27f81294c7.png]: https://img-blog.csdnimg.cn/459daf412ea447ecb3517c27f81294c7.png
[073fda1d2b214c3bb9a0046347df7157.png]: https://img-blog.csdnimg.cn/073fda1d2b214c3bb9a0046347df7157.png
[4cb4f74c12554abbafa65d0474e2ce07.png]: https://img-blog.csdnimg.cn/4cb4f74c12554abbafa65d0474e2ce07.png
[44625f552272452fa5639d7b14c1c6e4.gif]: https://img-blog.csdnimg.cn/44625f552272452fa5639d7b14c1c6e4.gif