题解 | #二叉搜索树与双向链表#

二叉搜索树与双向链表

http://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5

算法思想一：中序遍历+数组

解题思路：

主要思想是根据二叉树的中序遍历，并将遍历结果存储到数组中，再对数组进行遍历生成双向链表

1、特殊情况，如果二叉树为空，则返回 none

2、构建辅助数组 res 存储二叉树的中序遍历结果

3、遍历数组构建双向链表

res[i].right = res[i+1]
res[i+1].left = res[i]

4、返回 res[0]

图解：

代码展示：

Python版本

class Solution:
    def Convert(self, pRootOfTree):
        # write code here
        # 首先进行中序排序
        def inorder(root, res):
            if not root:
                return None
            inorder(root.left, res)
            res.append(root)
            inorder(root.right, res)
        res = []
        if not pRootOfTree:
            return None
        inorder(pRootOfTree, res)
        if len(res) == 1:
            return pRootOfTree
        # 构造双向链表
        for i in range(len(res)-1):
            res[i].right = res[i+1]
            res[i+1].left = res[i]
        return res[0]

复杂度分析

时间复杂度O(N)：N表示二叉树结点数量，遍历二叉树O(N)，遍历数组O(N)

空间复杂度O(N)：辅助数组占用额外空间

算法思想二：中序遍历优化

解题思路：

对方法一的改进：对于二叉树进行中序遍历，在遍历的同时调整结点之间的指针，使之成为双向链表

1、特殊情况，二叉树为空，则直接返回 null

2、创建保留上一个结点 pre，返回链表结点 root

3、递归遍历左子树；root = pRootOfTree

4、遍历当前结点，并修改为双向链表 pRootOfTree.left=pre; pre.right=pRootOfTree;

5、更新 pre = pRootOfTree

6、递归遍历右子树

7、递归结束返回 root

图解：

参考方法一图解，方法二只是在递归遍历二叉树的过程中进行修改结点指向生成双向链表

代码展示：

JAVA版本

public class Solution {
    TreeNode pre=null;
    TreeNode root=null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree==null)
            return null;
        // 递归遍历左子树
        Convert(pRootOfTree.left);
        // 判断特殊情况
        if (root==null){
            root=pRootOfTree;
        }
        // 修改遍历的结点为双向链表
        if (pre!= null){
            pRootOfTree.left=pre;
            pre.right=pRootOfTree;
        }
        // 更新 pre
        pre=pRootOfTree;
        // 递归遍历右子树
        Convert(pRootOfTree.right);
        return root;
    }
}