36.二叉搜索树与双向链表

参考链接

剑指offer_在线编程 -牛客网

剑指 Offer 36. 二叉搜索树与双向链表-跟着帅地玩转校招，刷爆各类算法题 - 帅地玩Offer

LCR 155. 将二叉搜索树转化为排序的双向链表 - 力扣（LeetCode）

个人尝试

看到二叉搜索树和将数据排序输出，尝试着中序遍历输出，结果符合预期

然后就使用 Carl 哥的中序遍历（统一迭代法，二叉树的统一迭代法 - 代码随想录）遍历二叉树，并将原先需要记录路径的处理改为处理左右指针

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val,Node _left,Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
class Solution {
    public Node treeToDoublyList(Node root) {
        if (root == null) return null;

        Deque<Node> stack = new LinkedList<>();
        Node cur = root, pre = null, head = null;
        stack.offerLast(root);
        while (!stack.isEmpty()) {
            if (stack.peekLast() != null) {
                Node tmp = stack.pollLast();
                if (tmp.right != null) stack.offerLast(tmp.right);

                stack.offerLast(tmp);
                //使用空节点标记已经遍历但还未处理的节点
                stack.offerLast(null);

                if (tmp.left != null) stack.offerLast(tmp.left);
            } else {
                // 弹出空节点
                stack.pollLast();
                cur = stack.pollLast();
                if (pre == null) {
                    head = cur;
                    pre = cur;
                } else {
                    pre.right = cur;
                    cur.left = pre;
                    pre = cur;
                }
            }
        }

        cur.right = head;
        head.left = cur;
        return head;
    }
}

不知道是不是自己代码有些部分写得有点冗余，执行计时击败 6.99%，消耗内存击败 5.17% 😂

优秀题解

中序遍历,递归版,代码还是蛮精简的!

class Solution {
    Node pre, head;
    public Node treeToDoublyList(Node root) {
        if(root == null) return null;
        dfs(root);
        head.left = pre;
        pre.right = head;
        return head;
    }
    void dfs(Node cur) {
        if(cur == null) return;
        dfs(cur.left);
        if(pre != null) pre.right = cur;
        else head = cur;
        cur.left = pre;
        pre = cur;
        dfs(cur.right);
    }
}

作者：Krahets
链接：https://leetcode.cn/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/solutions/186518/mian-shi-ti-36-er-cha-sou-suo-shu-yu-shuang-xian-5/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。