Description

Convert a binary search tree to doubly linked list with in-order traversal.

Example

Given a binary search tree:

    4

   / \

  2   5

 / \

1   3

return 1<->2<->3<->4<->5

5/11/2017

算法班

直接iterative in order traversal

1 /** 2  * Definition of TreeNode: 3  * public class TreeNode { 4  *     public int val; 5  *     public TreeNode left, right; 6  *     public TreeNode(int val) { 7  *         this.val = val; 8  *         this.left = this.right = null; 9  *     }10  * }11  * Definition for Doubly-ListNode.12  * public class DoublyListNode {13  *     int val;14  *     DoublyListNode next, prev;15  *     DoublyListNode(int val) {16  *         this.val = val;17  *         this.next = this.prev = null;18  *     }19  * }20  */ 21 public class Solution {22     /**23      * @param root: The root of tree24      * @return: the head of doubly list node25      */26     public DoublyListNode bstToDoublyList(TreeNode root) {  27         // Write your code here28         if (root == null) return null;29 30         Stack
     
       stack = new Stack
      
       ();31         TreeNode cur = root;32         DoublyListNode head = null;33         DoublyListNode prev = null;34         35         while (cur != null || !stack.empty()) {36             while (cur != null) {37                 stack.push(cur);38                 cur = cur.left;39             }40             cur = stack.pop();41             DoublyListNode node = new DoublyListNode(cur.val);42             if (head == null) {43                 head = node;44             }45             node.prev = prev;46             if (prev != null) {47                 prev.next = node;48             }49             cur = cur.right;50             prev = node;51         }52         return head;53     }54 }