题目描述
见题目
算法1
(dfs) $O(n)$
主要思路:
求出左子树里的最大值,加到自己左边。
再求出右子树里的最小值,加到自己右边。
实现方式:
把树遍历一遍,分四种情况:
1.左右子树都没有。返回{root, root}
2.左右子树都有。继续遍历左右子树,把左子树,root,右子树合成链表,返回{左子树的左孩子,右子树的右孩子}
3.只有左子树。继续遍历左子树,把左子树,root合成链表,返回{左子树的左孩子,root}
4.只有右子树。继续遍历右子树,把root,右子树合成链表,返回{root,右子树的右孩子}
把左子树里的最大值和右子树里的最小值放到pair里,当做函数的返回值。
参考文献
C++ 代码
class Solution {
public:
TreeNode* convert(TreeNode* root)
{
if (!root) return root;
auto sides = dfs(root);
return sides.first;
}
pair <TreeNode*, TreeNode*> dfs(TreeNode* root)
{
if (!root -> left && !root -> right) return {root, root};
if (root -> left && root -> right) {
auto lside = dfs(root->left), rside = dfs(root -> right);
lside.second -> right = root, root -> left = lside.second;
rside.first -> left = root, root -> right = rside.first;
return {lside.first, rside.second};
}
if (root -> left)
{
auto lside = dfs(root -> left);
lside.second -> right = root, root -> left = lside.second;
return {lside.first, root};
}
if (root -> right)
{
auto rside = dfs(root -> right);
rside.first -> left = root, root -> right = rside.first;
return {root, rside.second};
}
}
};
算法2
(中序遍历) $O(n)$
用一个pre指针保存中序遍历的前一个结点:
当前节点是根的时候,pre存的是左子树
当前节点是右子树的时候,pre存的是根
再把pre接到root前面就好了。
C++ 代码
class Solution {
public:
TreeNode* pre = NULL;
TreeNode* convert(TreeNode* root)
{
dfs(root);
while (root && root -> left) root = root -> left;
return root;
}
void dfs(TreeNode* root)
{
if (!root) return;
dfs(root -> left);
root -> left = pre;
if (pre) pre -> right = root;
pre = root;
dfs(root -> right);
}
};