算法
设一个二叉搜索树的前驱为prev、后继为next。
根据左右子树是否为NULL,分别更新前驱、后继。
时间复杂度: O(n)
空间复杂度: O(h)
C++代码
class Solution {
public:
static TreeNode *convert(TreeNode *root) {
if (root == NULL) {
return NULL;
}
TreeNode prev(0);
TreeNode next(0);
convert(root, &prev, &next);
prev.right->left = NULL;
next.left->right = NULL;
return prev.right;
}
static void convert(TreeNode *node, TreeNode *prev, TreeNode *next) {
if (node->left) {
convert(node->left, prev, node);
} else {
node->left = prev;
prev->right = node;
}
if (node->right) {
convert(node->right, node, next);
} else {
node->right = next;
next->left = node;
}
}
};
Java代码
class Solution {
static public TreeNode convert(TreeNode root) {
if (root == null) {
return null;
}
TreeNode prev = new TreeNode(0);
TreeNode next = new TreeNode(0);
convert(root, prev, next);
prev.right.left = null;
next.left.right = null;
return prev.right;
}
static public void convert(TreeNode node, TreeNode prev, TreeNode next) {
if (node.left != null) {
convert(node.left, prev, node);
} else {
node.left = prev;
prev.right = node;
}
if (node.right != null) {
convert(node.right, node, next);
} else {
node.right = next;
next.left = node;
}
}
}
Python3代码
class Solution(object):
def convert(self, root):
if root is None:
return None
prev = TreeNode(0)
next = TreeNode(0)
self.convert1(root, prev, next)
prev.right.left = None
next.left.right = None
return prev.right
def convert1(self, node, prev, next):
if node.left is not None:
self.convert1(node.left, prev, node)
else:
node.left = prev
prev.right = node
if node.right is not None:
self.convert1(node.right, node, next)
else:
node.right = next
next.left = node
C++代码 消除尾递归
采用消除尾递归的方法,减少函数递归调用层数。
仅 left && right 时,递归调用函数1次。
class Solution {
public:
static TreeNode *convert(TreeNode *root) {
if (root == NULL) {
return NULL;
}
TreeNode prev(0);
TreeNode next(0);
convert(root, &prev, &next);
prev.right->left = NULL;
next.left->right = NULL;
return prev.right;
}
static void convert(TreeNode *node, TreeNode *prev, TreeNode *next) {
for (;;) {
TreeNode *const left = node->left;
TreeNode *const right = node->right;
if (!left) {
node->left = prev;
prev->right = node;
}
if (!right) {
node->right = next;
next->left = node;
}
if (right) {
if (left) {
convert(node->left, prev, node);
}
prev = node;
node = node->right;
} else if (left) {
next = node;
node = node->left;
} else {
return;
}
}
}
};