【剑指Offer】T36 二叉搜索树和双向链表

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

思路:思路借鉴二叉树的中序线索化(二叉排序树中序序列为有序)

  • 线索化函数 helper
    • 左子树线索化
    • 进行连接
      • p->left指向pre
      • pre不为空时,指向p
      • p地址到pre以便下一次递归
    • 右子树线索化
  • 主函数调用递归函数
  • 返回最左节点(调用线索化函数后直接返回并不是完整的序列)
  • 需要注意的是 pre 必须定义为应用类型,不然下次递归并不会和上次递归有连接
/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/

class Solution {
public:
    void Helper(TreeNode* node, TreeNode* &pre){
        if(!node)
            return nullptr;
        
        // 左子树线索化
        Helper(node->left, pre);
        
        // 线索化过程
        node->left = pre;
        if(pre)
            pre->right = node;
        pre = node;
        
        Helper(p->right, pre);
    }
    
    
    TreeNode* Convert(TreeNode* pRootOfTree){
        if(!pRootOfTree)
            return nullptr;
        // 第一个pre肯定为空
        TreeNode* pre = nullptr;
        Helper(pRootOfTree, pre);
        
        // 找到最左节点
        TreeNode* list = pRootOfTree;
        while(list->left)
            list = list->left;
        return list;
    }
}

本文链接:https://ariser.cn/index.php/archives/387/
本站文章采用 知识共享署名4.0 国际许可协议进行许可,请在转载时注明出处及本声明!