binarySearchTreetoDoublyLinkedList

题目：
convert a binary tree to doubly linked list

解题思路：
这道题其实就是用stack+中序遍历来解决。这道题还有第二种解法，就是用recursive dfs然后返回最后一个node。

代码：

public class BSTtoDoubleLinkedList {

    static class TreeNode{
        public int val;
        public TreeNode left, right;
        public TreeNode(int val){
            this.val = val;
            this.left = this.right = null;
        }
    }

    static class DoublyListNode{
        public int val;
        DoublyListNode next, prev;
        DoublyListNode(int val){
            this.val = val;
            this.next = this.prev = null;
        }
    }

    public static void main(String[] args){
        TreeNode node4 = new TreeNode(4);
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);

        node1.right = node2;
        node3.left = node1;
        node6.left = node5;
        node6.right = node7;
        node4.left = node3;
        node4.right = node6;

        DoublyListNode result = bstToDoublyList(node4);
        print(result);

    }

    /**     
    * @param root: The root of tree     
    * @return: the head of doubly list node     
    */    
    public static DoublyListNode bstToDoublyList(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode treeCurr = root;
        DoublyListNode dummy = new DoublyListNode(0);
        DoublyListNode curr = dummy;
        while(!stack.isEmpty() || treeCurr != null){
            while(treeCurr.left != null){
                TreeNode temp = treeCurr;
                treeCurr = treeCurr.left;
                temp.left = null;
                stack.push(temp);
            }
            DoublyListNode next = new DoublyListNode(treeCurr.val);
            curr.next = next;
            curr = next;
            if(treeCurr.right == null && !stack.isEmpty()){
                treeCurr = stack.pop();
            }
            else{
                treeCurr = treeCurr.right;
            }
        }

        return dummy.next;
    }

    private static void print(DoublyListNode node){
        while(node != null){
            System.out.println(" " + node.val);
            node = node.next;
        }
    }
}