897. Increasing Order Search Tree 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    private static class TreeNodeHolder {
        private TreeNode pre;
    }

    public TreeNode increasingBST(TreeNode root) {
        TreeNodeHolder treeNodeHolder = new TreeNodeHolder();
        TreeNode dummyHead = new TreeNode();
        treeNodeHolder.pre = dummyHead;
        dfs(treeNodeHolder, root);
        return dummyHead.right;
    }

    private void dfs(TreeNodeHolder treeNodeHolder, TreeNode node) {
        if (node == null) {
            return;
        }

        dfs(treeNodeHolder, node.left);
        node.left = null; // 防止成环
        treeNodeHolder.pre.right = node;
        treeNodeHolder.pre = node;
        dfs(treeNodeHolder, node.right);
    }
}

References

897. Increasing Order Search Tree
剑指 Offer II 052. 展平二叉搜索树