输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
思路
代码
- 中序遍历 + 分治 + 递归，每个分治部分返回链表的头结点，所以要移动到左边链表的最后结点再和根结点连接，右链表头结点直接和根结点连接
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public TreeNode Convert(TreeNode root) {
if (root == null) {
return null;
}
if (root.left == null && root.right == null) {
return root;
}
TreeNode left = Convert(root.left);
TreeNode node = left;
while (node != null && node.right != null) {
node = node.right;
}
if (left != null) {
node.right = root;
root.left = node;
}
TreeNode right = Convert(root.right);
if (right != null) {
right.left = root;
root.right = right;
}
return left == null ? root : left;
}
}
- 中序遍历 + 非递归
import java.util.*;
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public TreeNode Convert(TreeNode root) {
if (root == null) {
return null;
}
if (root.left == null && root.right == null) {
return root;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode node = root;
TreeNode preNode = null;
TreeNode FirstNode = null;
boolean isFirst = true;
while (node != null || !stack.isEmpty()) {
while (node != null) {
stack.push(node);
node = node.left;
}
node = stack.pop();
if (isFirst) {
FirstNode = node;
preNode = node;
isFirst = false;
} else {
node.left = preNode;
preNode.right = node;
preNode = node;
}
node = node.right;
}
return FirstNode;
}
}
