二叉搜索树和双向链表

时间:2022-07-05 09:51:21

题目描述

输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。 
//二叉搜索树转换成双向链表.
 //二叉树当前结点的左指针应指向该结点左子树中最右孩子的结点;同时最右孩子的右指针应指向当前结点;
 //二叉树当前结点的右指针应指向该结点右子树中最左孩子的结点;同时最左孩子的左指针应指向当前结点;
 public TreeNode Convert(TreeNode pRootOfTree) {
     if(pRootOfTree==null)
        return null;
     if(pRootOfTree.left==null&&pRootOfTree.right==null)
        return pRootOfTree;
     TreeNode head=null;
     if(pRootOfTree.left!=null)
     { 
         TreeNode left= Convert(pRootOfTree.left);           
         TreeNode tmp=left;            
         while(tmp.right!=null)      
             tmp=tmp.right;     
         tmp.right=pRootOfTree;  
         pRootOfTree.left=tmp;
    }
 
    if(pRootOfTree.right!=null)
    {
        TreeNode right=Convert(pRootOfTree.right);
        TreeNode tmp=right;
        while(tmp.left!=null)
            tmp=tmp.left;
        tmp.left=pRootOfTree;
        pRootOfTree.right=tmp;
     
    }
    //返回链表的头指针
     while(pRootOfTree.left!=null)
         pRootOfTree=pRootOfTree.left;
    return pRootOfTree;
}

  

 

class Solution {
public:
    TreeNode* Convert(TreeNode* pRootOfTree)
    {
        //若不存在,直接返回空指针
        if(!pRootOfTree)
            return nullptr;
        //left代表左子树的最左指针,right代表右子树的最右指针
        TreeNode *left = nullptr, *right = nullptr;
        //若左子树存在,求左子树最左边的指针
        if(pRootOfTree->left)
            left = Convert(pRootOfTree->left);
        //若右子树存在,求右子树的最左边的指针
        if(pRootOfTree->right)
            right = Convert(pRootOfTree->right);
        //先假定最终双向链表的头指针为当前根节点指针
        TreeNode *newRoot = pRootOfTree;
        //若左子树的最左边指针存在,left就是newRoot,进行链接
        if(left)
        {
            newRoot = left;
            while(left->right)
                left = left->right;
            left->right = pRootOfTree;
            pRootOfTree->left = left;
        }
        //无论右子树最右指针存不存在,都将当前指针指向右子树最右指针
        pRootOfTree->right = right;
       //若右子树最左的指针存在,则进行链接操作
        if(right)
            right->left = pRootOfTree;
        //返回新双向链表的头节点
        return newRoot;
    }
};

  

 

/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
public:
TreeNode* Convert(TreeNode* pRootOfTree)
{
if(pRootOfTree == NULL)return NULL;
TreeNode *pre=NULL;
convertHelper(pRootOfTree,pre);
TreeNode * res=pRootOfTree;
while(res->left)
res=res->left;
return res;

}

void convertHelper(TreeNode * cur,TreeNode*& pre) {
if(cur==NULL)return;
convertHelper(cur->left,pre);
cur->left = pre;
if(pre)pre->right=cur;
pre=cur;
convertHelper(cur->right,pre);
}
};