2021/2/28 剑指 Offer 36. 二叉搜索树与双向链表

题目描述

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

我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。

下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。

特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。

解题思路

1. 二叉搜索树从小到大排列，一下子联想到 DFS，既然是DFS，那就用栈和递归吧。
2. 用中序遍历把元素全压进栈，遍历完了再弹出来，弹出来的时候维护两个指针，让两个元素互相指认一下自己的邻居。

Java代码实现

import java.util.Stack;
public class Solution {
    // 用栈保存元素
    Stack<TreeNode> stack = new Stack<TreeNode>();
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) return null;
        func(pRootOfTree);
        return sort();

    }

    // 中序遍历
    public void func(TreeNode node) {
        if (node == null) return;
        func(node.left);
        stack.push(node);
        func(node.right);
    }

    // 邻居互相指认环节，连接相邻的两个元素
    public TreeNode sort() {
        TreeNode cur = stack.pop();
        cur.right = null;
        while (!stack.empty()) {
            TreeNode node = stack.pop();
            cur.left = node;
            node.right = cur;
            cur = node;
        }
        return cur;
    }
}