FG面经Prepare: BST to Double LinkedList

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, 改指针就好了