给你一棵二叉搜索树,请你 按中序遍历 将其重新排列为一棵递增顺序搜索树,使树中最左边的节点成为树的根节点,并且每个节点没有左子节点,只有一个右子节点。
二叉树的题要记得保存好头指针result,用新的指针ans复制后去遍历,防止遍历影响头指针
设立result作为结果的头指针,然后ans等于它;
ans的右指针等于root,将root的左孩子设置为空,并成为新的ans
TreeNode* increasingBST(TreeNode* root) { TreeNode* result=new TreeNode(0); ans=result;//ans负责递归往后接,result永远指向最初节点 inroder(root); return result->right; } void inroder(TreeNode* root){ if(root==nullptr) return; inroder(root->left); ans->right=root; root->left=nullptr;//root左孩子置空 ans=root; inroder(root->right); }
或者 在dfs函数里重新节点(时间最短)
void inroder(TreeNode* root){ if(root==nullptr) return; inroder(root->left); ans->right=new TreeNode(root->val);//root的值作为新的节点的值 ans=ans->right; inroder(root->right); } };
另一种,普通中序遍历,然后每次把val放进数组
通过数组数据重建二叉树
class Solution { public: vector<int> temp; TreeNode* increasingBST(TreeNode* root) { inroder(root); TreeNode* result=new TreeNode(0); TreeNode* ans=result;//用ans进行循环,保留住result的位置 for(auto i:temp){ ans->left=nullptr; ans->right=new TreeNode(i); ans=ans->right; } return result->right; } void inroder(TreeNode* root){ if(root==nullptr) return; inroder(root->left); temp.push_back(root->val); inroder(root->right); } };