剑指Offer(7)[BinaryTree]二叉搜索树转换双向链表

输入一棵二叉搜索树&＃xff0c;将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点&＃xff0c;只能调整树中结点指针的指向。

思路

第一种思路比较直观&＃xff0c;使用一个容器收集中序遍历结果&＃xff0c;并且将其连接成双向链表即可&＃xff0c;这种做法会使用额外的空间复杂度。

第二种思路是通过栈实现中序遍历&＃xff0c;在每次中序遍历过程中获取当前节点&＃xff0c;并让当前节点和上一个节点相连&＃xff0c;并将当前节点设置为上一个节点。这样的做法只需要中序遍历一次即可获取到双线链表&＃xff0c;并且不需要使用容器存储整个链表&＃xff0c;节约空间。

Java第一种解法【额外的空间复杂度】

/**
public class TreeNode {int val &＃61; 0;TreeNode left &＃61; null;TreeNode right &＃61; null;public TreeNode(int val) {this.val &＃61; val;}
}
*/
import java.util.*;
public class Solution {public TreeNode Convert(TreeNode root) {if (root &＃61;&＃61; null) {return null;}// 中序遍历获取到排序的树节点数组ArrayList<TreeNode> list &＃61; new ArrayList<>();inorder(root, list);// 将中间部分节点依次首位连接for (int i &＃61; 1; i < list.size() - 1; i&＃43;&＃43;) {TreeNode node &＃61; list.get(i);node.left &＃61; list.get(i - 1);node.right &＃61; list.get(i &＃43; 1);}// 处理头节点list.get(0).left &＃61; null;list.get(0).right &＃61; (list.size() > 1) ? list.get(1) : null;// 处理尾节点list.get(list.size() - 1).left &＃61; (list.size() > 1) ? list.get(list.size() - 2) : null;list.get(list.size() - 1).right &＃61; null;return list.get(0);}private void inorder(TreeNode root, ArrayList<TreeNode> list) {if (root &＃61;&＃61; null) {return;}inorder(root.left, list);list.add(root);inorder(root.right, list);}
}


Java第二种解法【使用栈做中序遍历】

/**
public class TreeNode {int val &＃61; 0;TreeNode left &＃61; null;TreeNode right &＃61; null;public TreeNode(int val) {this.val &＃61; val;}}
*/
import java.util.*;
public class Solution {public TreeNode Convert(TreeNode root) {if (root &＃61;&＃61; null) {return null;}// 中序遍历获取到排序的树节点数组TreeNode res &＃61; null;TreeNode pre &＃61; null;boolean first &＃61; true;Stack<TreeNode> stack &＃61; new Stack<>();while (!stack.isEmpty() || root !&＃61; null) {if (root !&＃61; null) {stack.push(root);root &＃61; root.left;} else {TreeNode pop &＃61; stack.pop();if (first) {// 是第一个节点res &＃61; pop;pre &＃61; pop;pop.left &＃61; null;first &＃61; false;} else {// 是中间节点或尾节点&＃xff0c;前后相连pre.right &＃61; pop;pop.left &＃61; pre;// 将当前节点置为前一个节点pre &＃61; pop;}root &＃61; pop.right;}}return res;}
}