BST to double linkedlist in inorder traversal sequence Follow Up: 如果这个BST自带prev, next, 给一个value，插进去这个node，并补全left，right，prev，next

 

1 class TreeNode { 2  public int val; 3  TreeNode left; 4  TreeNode right; 5 } 6  7 TreeNode newRoot 8  9 TreeNode tree2Dll(TreeNode root) {10   TreeNode pre = null;11   TreeNode newRoot = null;12   helper(root, pre);13   return newRoot;14 }15 16 public void helper(TreeNode cur, TreeNode pre) {17   if (cur == null) {18     return;19   }20   helper(cur.left, pre);21   cur.left = pre;22   if (pre == null) {23      newRoot = cur;24   }25   else pre.right = cur;26   pre = cur;27   helper(cur.right, pre, newRoot);28 }

 

Follow up:

第一步完成基础上，把这个new value插入BST中，一边插入一边记录沿途的大于value的root node（即走了该root node的left child），作为inorder successor. 找到inorder successor之后，通过其prev指针找到inorder predecessor, 改指针就好了