描述

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。如下图所示

数据范围：输入二叉树的节点数 0 \le n \le 10000≤n≤1000，二叉树中每个节点的值 0\le val \le 10000≤val≤1000
要求：空间复杂度O(1)O(1)（即在原树上操作），时间复杂度 O(n)O(n)

我的解法：

        二叉搜索树的中序遍历正好为排序的结果，通过中序遍历，递归过程中，通过pre节点保存上一节点数据，完成转换

/**
public class TreeNode {int val = 0;TreeNode left = null;TreeNode right = null;public TreeNode(int val) {this.val = val;}}
*/    
TreeNode pre = null;public TreeNode Convert(TreeNode pRootOfTree) {if (pRootOfTree == null) return null;a(pRootOfTree);TreeNode p = pRootOfTree;while (p.left != null) {p = p.left;}return p;}//按照中序遍历正好是排序的 4 6 8 10 12 14 16public void a(TreeNode root){if(root==null){return;}a(root.left);root.left=pre;//当前节点的左边指向上一个节点if(pre!=null){pre.right=root;//如果上一个节点不为空，让上一个节点的右边指向当前节点}pre=root;//设置新的节点a(root.right); }