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

题意分析

• 给出一棵二叉树，我们需要按照这棵树的节点的权值的大小先进行升序排序，然后在不改新增节点的前提下将它改为一条双向链表。原来的左指针作为一个前驱指针，右指针作为一个后继指针。

思路分析

解法一

• 对于这个题目，一开始想的是用一个map存储每个数字对应的一个节点，这种的思路其实是有问题的，就是如果存在相同的数字的话那么就可能会出错。但写出来发现竟然可以过，所以我觉得这个题目的数据可能比较弱。来说说具体的写法吧。我们先将所以的权值存入一个数组，然后进行排序，同时我们记录每个数字对应的节点。所以在这之后，我们就可以对数组进行遍历，然后不断更新每个节点的左右指针即可。同时注意首尾位置的指针。
• 代码

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:
    vector<int> v;
    map<int,TreeNode*> mp;
    // 存储每个节点的权值
    void dfs(TreeNode* root){  
        mp[root->val]=root;
        // map存储，一个数字对应一个节点指针
        v.push_back(root->val);  
        if(root->left){
            dfs(root->left);
        }
        if(root->right){
            dfs(root->right);
        }
    }
    TreeNode* Convert(TreeNode* pRootOfTree) {
        if(!pRootOfTree){
            return NULL;
        }
        dfs(pRootOfTree);
        // 先进行排序
        sort(v.begin(),v.end());  
        int n=v.size();
        mp[v[0]]->left=NULL;
        mp[v[0]]->right=mp[v[1]];
        for(int i=1;i<n-1;i++){
            mp[v[i]]->left=mp[v[i-1]];
            mp[v[i]]->right=mp[v[i+1]];
        }
        mp[v[n-1]]->left=mp[v[n-2]];
        mp[v[n-1]]->right=NULL;
        return mp[v[0]];
    }
};

解法二

• 我们发现，这个题目给出的是一棵二叉搜索树，所以其实这棵二叉树在一定程度上是有序的，那么我们如何利用二叉搜索树有序的条件呢？我们发现，对二叉树进行中序遍历之后的结果就是一个有序的序列了。我们进行中序遍历的时候，我们用一个pre指针表示访问的前一个节点，现在访问的节点叫做root，我们可以发现他们之间的关系是这样的，上一个访问的那个节点的权值肯定在现在访问的左边并且相邻。如下图

所以我们可以不断更新每个节点的左右指针即可。

• 代码

  /*
  struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
  };*/
  class Solution {
  public:
    TreeNode* pre=NULL;
    // 进行一个中序遍历
    void InOrder(TreeNode* root){
        if(!root){
            return;
        }
         // 不断向下递归
        InOrder(root->left); 
        // 现在遍历的节点的左节点是上一个节点
        root->left=pre;  
        if(pre){  
             // 上一个遍历的节点的右节点是现在这个节点
            pre->right=root; 
        }
        pre=root;
        InOrder(root->right);
    }
    TreeNode* Convert(TreeNode* pRootOfTree) {
        if(!pRootOfTree){
            return NULL;
        }
        TreeNode* last=pRootOfTree;
        while(last->left){
            last=last->left;
        }
        InOrder(pRootOfTree);
        return last;
    }
  };