leetcode 897. Increasing Order Search Tree（增序搜索树）_综合

题目要求

给定一棵树，按顺序重新排列树，以便树中最左边的节点现在是树的根，并且每个节点都没有左子，只有一个右子。如下图：
在这里插入图片描述

解题思路

因为最后的输出要按照从低到高的顺序，而给出的BST按照先序遍历正好是增序排列，所以我们解题的思路就是按照先序遍历得到节点的值，然后根据节点的值建立新树，最后输出即可。

注意：左节点是NULL！

主要代码c++

/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
    
public:vector<int>result;TreeNode* increasingBST(TreeNode* root) {
    inorder(root);TreeNode *head = new TreeNode(0);TreeNode *p = head;for(int i = 0; i < result.size(); ++i, p=p->right) // 建立新树p->right = new TreeNode(result[i]);return head->right;}void inorder(TreeNode* root){
     // 先序遍历if(root==NULL) return;inorder(root->left);result.push_back(root->val);inorder(root->right);}
};