题目描述
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
思路
题目要求转换成排序后的双向链表，根据二叉搜索树的性质，值的大小：左子树<根节点<右子树。因此遍历方式为 中序遍历，中序遍历有 递归实现 和 非递归实现。
思路1：中序遍历二叉树，然后用一个ArrayList保存遍历的结果，这样节点就按顺序保存了，最后修改前后指针。 （最常规的思路，但使用额外的数据结构）
思路2：把树分成3部分：根节点，左子树和右子树。然后把左子树中最大的节点、根节点、右子树中最小的节点链接起来。递归实现左子树和右子树内部的节点链接成链表。 （剑指书上的思路）
思路3：二叉搜索树的中序遍历就是有序序列，因此遍历时将当前节点与前一个节点进行连接即可。定义全局变量记录当前链表的末尾节点。 （最优解，中序遍历的精髓呐！～）
解法1（对应思路1）
/** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */ import java.util.ArrayList; import java.util.Stack; public class Solution { public TreeNode Convert(TreeNode pRootOfTree) { if (pRootOfTree == null) return null; ArrayList<TreeNode> list = new ArrayList<TreeNode>(); InOrder(pRootOfTree,list); for (int i = 0; i < list.size() - 1; i++){ list.get(i).right = list.get(i+1); list.get(i+1).left = list.get(i); } return list.get(0); } /* * 递归实现中序遍历 * 先一直向左遍历，直到为空时返回并且打印最左边的节点。 */ private void InOrder(TreeNode pRootOfTree,ArrayList<TreeNode> list){ if (pRootOfTree == null) return; InOrder(pRootOfTree.left,list); list.add(pRootOfTree); // list保存的是对象的引用或地址 InOrder(pRootOfTree.right,list); } // 非递归实现中序遍历 private void InOrder(TreeNode pRootOfTree,ArrayList<TreeNode> list){ Stack<TreeNode> stack = new Stack<TreeNode>(); TreeNode cur = pRootOfTree; while (cur != null || !stack.isEmpty()){ while (cur != null){ stack.push(cur); cur = cur.left; } cur = stack.pop(); list.add(cur); cur = cur.right; } } }
☆解法2（对应思路2）
/** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */ public class Solution { /* * ----------解法2 递归---------- * 已知函数返回的是转换好的双向链表头结点 * 左子树处理完后与根结点连接 * 右子树处理，也与根结点连接 * 最后返回头结点 */ public TreeNode Convert(TreeNode root) { if (root == null) return null; // 1.将左子树构造成双链表，并返回链表头节点 TreeNode left = Convert(root.left); TreeNode p = left; if (left != null){ // 2.定位至左子树双链表最后一个节点 while (p.right != null) p = p.right; // 3.将当前root追加到左子树链表 p.right = root; root.left = p; } // 4.将右子树构造成双链表，并返回链表头节点 TreeNode right = Convert(root.right); // 5.如果右子树链表不为空的话，将该链表追加到root节点之后 if (right != null){ root.right = right; right.left = root; } return left == null ? root : left; // 返回头节点 } }
☆☆☆解法3（对应思路3）
/** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */ import java.util.Stack; public class Solution { /* *----------- 递归版本 ----------- */ private TreeNode pLast = null; // 记录当前链表的末尾节点。 public TreeNode Convert(TreeNode root) { if (root == null) return null; // 如果左子树为空，那么根节点root为双向链表的头节点 TreeNode head = Convert(root.left); if (head == null) head = root; // 连接当前节点root和当前链表的尾节点pLast root.left = pLast; if (pLast != null) pLast.right = root; pLast = root; Convert(root.right); return head; } /* * ------------非递归版本----------- */ public TreeNode Convert(TreeNode root) { if (root == null) return null; Stack<TreeNode> stack = new Stack<TreeNode>(); TreeNode cur = root; TreeNode pre = null; // 保存中序遍历序列的上一节点 boolean isFirst = true; while (cur != null || !stack.isEmpty()){ while (cur != null){ stack.push(cur); cur = cur.left; } cur = stack.pop(); if (isFirst){ root = cur; // 将中序遍历序列中的第一个节点即为root pre = cur; isFirst = false; }else{ pre.right = cur; cur.left = pre; pre = cur; } cur = cur.right; } return root; } }