链接
https://leetcode-cn.com/problems/increasing-order-search-tree/
耗时
解题：31 min
题解：17 min
题意
给你一棵二叉搜索树，请你 按中序遍历 将其重新排列为一棵递增顺序搜索树，使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。
提示：
- 树中节点数的取值范围是 [1, 100]
- 0 <= Node.val <= 1000
思路
维护一个 上一节点 的指针，这一指针指向当前节点在 答案树 中它的父节点。
初始化这个指针指向空，当找到最左子节点时，第一次给 上一节点 的指针赋值；并把最左子节点记录下来，这就是题意要返回的 头节点。
dfs遍历访问节点时就把 上一节点 的左子节点指向空，右子节点指向当前节点。然后再把当前节点赋给 上一节点 。直到遍历结束。
细节： 遍历结束需要把 上一节点 的左子节点置空，否则可能会造成一个 环，并且答案也就不对了。
时间复杂度：
O
(
n
)
O(n)
O(n)
AC代码
class Solution {
private:
TreeNode* last_node;
TreeNode* head_node;
public:
void dfs(TreeNode* root) {
if(root == NULL) return ;
dfs(root->left);
if(last_node != NULL) {
last_node->left = NULL;
last_node->right = root;
}
else {
head_node = root;
}
last_node = root;
dfs(root->right);
}
TreeNode* increasingBST(TreeNode* root) {
dfs(root);
last_node->left = NULL;
return head_node;
}
};
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
