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

1、解题思路

1. 中序遍历：二叉搜索树的中序遍历结果是升序的，因此可以通过中序遍历来调整指针。使用递归或迭代方法进行中序遍历，同时记录前驱节点 prev，并在遍历过程中调整指针。
2. 指针调整：遍历过程中，当前节点的 left 指针指向 prev。prev 的 right 指针指向当前节点（如果 prev 不为空）。更新 prev 为当前节点。
3. 头节点处理：链表的最左节点（最小值）即为双向链表的头节点，可以通过遍历找到最左节点。

2、代码实现

C++（递归）

/*
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 == nullptr) {
            return nullptr;
        }

        // 中序遍历调整指针
        inorder(pRootOfTree);

        // 找到链表的头节点 (最左节点)
        TreeNode* head = pRootOfTree;
        while (head->left != nullptr) {
            head = head->left;
        }

        return head;
    }

  private:
    TreeNode* prev = nullptr;   // 前驱节点

    void inorder(TreeNode* node) {
        if (node == nullptr) {
            return ;
        }

        inorder(node->left);    // 遍历左子树

        // 调整指针
        node->left = prev;
        if (prev != nullptr) {
            prev->right = node;
        }
        prev = node;    // 更新前驱节点

        inorder(node->right);   // 遍历右子树
    }
};

C++（迭代）

/*
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 == nullptr) {
            return nullptr;
        }

        stack<TreeNode*> s;
        TreeNode* prev = nullptr;
        TreeNode* cur = pRootOfTree;
        TreeNode* head = nullptr;

        while (cur != nullptr || !s.empty()) {
            while (cur != nullptr) {
                s.push(cur);
                cur = cur->left;
            }

            cur = s.top();
            s.pop();

            // 找到头节点 (最左节点)
            if (prev == nullptr) {
                head = cur;
            } else {
                prev->right = cur;
                cur->left = prev;
            }

            prev = cur;
            cur = cur->right;
        }

        return head;
    }
};

Java（递归）

import java.util.*;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) return null;

        inorder(pRootOfTree);

        // 找到头节点（最左节点）
        TreeNode head = pRootOfTree;
        while (head.left != null) {
            head = head.left;
        }

        return head;
    }

    private TreeNode prev = null;

    private void inorder(TreeNode node) {
        if (node == null) return;

        inorder(node.left);

        node.left = prev;
        if (prev != null) {
            prev.right = node;
        }
        prev = node;

        inorder(node.right);
    }
}

Java（迭代）

import java.util.*;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
import java.util.Stack;

public class Solution {
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) return null;

        Stack<TreeNode> stack = new Stack<>();
        TreeNode prev = null;
        TreeNode curr = pRootOfTree;
        TreeNode head = null;

        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }

            curr = stack.pop();

            if (prev == null) {
                head = curr;
            } else {
                prev.right = curr;
                curr.left = prev;
            }

            prev = curr;
            curr = curr.right;
        }

        return head;
    }
}

Python（递归）

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

#
#
# @param pRootOfTree TreeNode类
# @return TreeNode类
#
class Solution:
    def __init__(self):
        self.prev = None

    def Convert(self, pRootOfTree):
        # write code here
        if not pRootOfTree:
            return None

        self.inorder(pRootOfTree)

        # 找到头节点（最左节点）
        head = pRootOfTree
        while head.left:
            head = head.left

        return head

    def inorder(self, node):
        if not node:
            return

        self.inorder(node.left)

        node.left = self.prev
        if self.prev:
            self.prev.right = node
        self.prev = node

        self.inorder(node.right)

Python（迭代）

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

#
# 
# @param pRootOfTree TreeNode类 
# @return TreeNode类
#
class Solution:
    def Convert(self , pRootOfTree ):
        # write code here
        if not pRootOfTree:
            return None
        
        stack = []
        prev = None
        curr = pRootOfTree
        head = None
        
        while curr or stack:
            while curr:
                stack.append(curr)
                curr = curr.left
            
            curr = stack.pop()
            
            if not prev:
                head = curr
            else:
                prev.right = curr
                curr.left = prev
            
            prev = curr
            curr = curr.right
        
        return head

3、复杂度分析

• 时间复杂度：O(n)，每个节点被访问一次。
• 空间复杂度：递归方法为 O(h)（树高），迭代方法为 O(n)（最坏情况下栈存储所有节点）。