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

Recursion

class Solution {
    private static class NodeHolder {
        private Node head;
        private Node pre;
    }

    public Node treeToDoublyList(Node root) {
        if (root == null) {
            return null;
        }

        // left -> root -> right
        NodeHolder nodeHolder = new NodeHolder();

        dfs(nodeHolder, root);

        Node tail = nodeHolder.pre;
        nodeHolder.head.left = tail;
        tail.right = nodeHolder.head;

        return nodeHolder.head;
    }

    private void dfs(NodeHolder nodeHolder, Node node) {
        if (node == null) {
            return;
        }

        dfs(nodeHolder, node.left);

        if (nodeHolder.pre == null) {
            nodeHolder.head = node;
        } else {
            node.left = nodeHolder.pre;
            nodeHolder.pre.right = node;
        }

        nodeHolder.pre = node;

        dfs(nodeHolder, node.right);
    }
}

Iterate

class Solution {
    public Node treeToDoublyList(Node root) {
        // left -> root -> right

        if (root == null) {
            return null;
        }

        Stack<Node> stack = new Stack<>();
        Node head = null, pre = null;
        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }

            // now: root is null
            Node node = stack.pop();
            if (head == null) {
                head = node;
            }
            if (pre != null) {
                pre.right = node;
                node.left = pre;
            }
            pre = node;

            root = node.right;
        }

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

Reference

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