剑指offer26-二叉搜索树与双向链表

题目描述

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

知识点

递归

比如将二元查找树
                                            10
                                          /    
                                        6       14
                                      /         /  
                                    4     8  12  16
转换成双向链表
4=6=8=10=12=14=16。

1.二叉树中序遍历的结果与链表的顺序一致，所以可以采用中序遍历的方法来修改二叉树的指针

2.该题的关键是，如何将左子树的最大值与右子树的最小值通过根root连接起来，比如题目的8和12，这也是细节部分

3.写递归程序最重要的是弄明白递归进入的条件、递归返回的状态，如果递归进入时改变了环境，返回时应当恢复环境，就像栈的操作一样

4.使用指针变量时，要记得初始化

5.算法最后返回链表头，而不是返回root。

非递归：中序遍历

参考https://blog.csdn.net/endif6/article/details/82356035(之后添加)

代码

#递归法
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def Convert(self, pRootOfTree):
        # write code here
        if pRootOfTree==None:
            return None
        if pRootOfTree.left==None and pRootOfTree.right==None:
            return pRootOfTree
        self.Convert(pRootOfTree.left)    #处理左子树
        left=pRootOfTree.left
        while left and left.right:        #找到左子树最右边（最大）节点left
            left=left.right
        if pRootOfTree.left:              #双向连接left和根节点
            left.right=pRootOfTree
            pRootOfTree.left=left
        self.Convert(pRootOfTree.right)   #处理右子树
        right=pRootOfTree.right
        while right and right.left:       #找到右子树最左边（最小）节点right
            right=right.left
        if pRootOfTree.right:             #双向连接right和根节点
            right.left=pRootOfTree
            pRootOfTree.right=right
        while(pRootOfTree.left):          #找到双向链表头
            pRootOfTree = pRootOfTree.left
        return pRootOfTree