January 01, 2020

426. Convert Binary Search Tree to Sorted Doubly Linked List

Inorder traversal. Refer to: 94. Binary Tree Inorder Traversal

Sol 1. Recursion

这个视频讲解的很清楚。

Time = O(n)
Space = (n) -> keep a recursion stack of the size of the tree height, which is O(logn) for the best case and O(n) for the worst case.

/*
// 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 {
    Node pre = null;
    Node head = null;
    Node tail = null;
    public Node treeToDoublyList(Node root) {
        if (root == null) {
            return null;
        }
        inorder(root);
        head.left = tail;
        tail.right = head;
        return head;
    }
    
    private void inorder(Node root) {
        if (root == null) {
            return;
        }
        
        inorder(root.left);
        if (pre == null) {
            pre = root;
            head = root;
        } else {
            pre.right = root;
            root.left = pre;
            pre = root;
        }
        tail = root;
        inorder(root.right);
    }
}

Sol 2. Iterative

参考视频讲解

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

    public Node() {}

    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;
        }
        Node pre = null;
        Node head = null;
        Deque<Node> stack = new ArrayDeque<>();
        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                stack.offerFirst(root);
                root = root.left;
            }
            root = stack.pollFirst();
            if (pre == null) {
                head = root;
            } else {
                pre.right = root;
                root.left = pre;
            }
            pre = root;
            root = root.right;
        }
        pre.right = head;
        head.left = pre;
        return head;
    }
}