LeetCode_897_遞增順序查找樹

題目描述：

給定一個樹，按中序周遊重新排列樹，使樹中最左邊的結點現在是樹的根，并且每個結點沒有左子結點，隻有一個右子結點。

 

示例 ：

輸入：[5,3,6,2,4,null,8,1,null,null,null,7,9]

       5
      / \
    3    6
   / \    \
  2   4    8
 /        / \ 
1        7   9

輸出：[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

 1
  \
   2
    \
     3
      \
       4
        \
         5
          \
           6
            \
             7
              \
               8
                \
                 9  
 

提示：

給定樹中的結點數介于 1 和 100 之間。
每個結點都有一個從 0 到 1000 範圍内的唯一整數值。      

思想：建構一棵新樹，代替原來的樹

/**
 * 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:
    TreeNode* newroot, *curr;
    TreeNode* increasingBST(TreeNode* root) {
        if (root == NULL) return NULL;
        increasingBST(root->left);
        if (newroot == NULL) { 
            newroot = new TreeNode(root->val);
            curr = newroot;
        }
        else {
            curr->right = new TreeNode(root->val);
            curr=curr->right;
        }
        increasingBST(root->right);
        return newroot;
    }
};      

/**
 * 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:
    TreeNode *ans,*pre;//定義指針節點,定義成成員變量，會調用預設的構造函數，指派為NULL
    void inorder(TreeNode* root,vector<int> &res){
        if(root==NULL)
            return ;
        inorder(root->left,res);
        res.push_back(root->val);
        inorder(root->right,res);
    }
    TreeNode* increasingBST(TreeNode* root) {
        if(root==NULL)
            return NULL;
        vector<int> res;
        inorder(root,res);
        //TreeNode *ans,*pre;在内部，不會調用構造函數，必須賦予初始值NULL
        for(int i=0;i<res.size();i++){
            if(ans==NULL){
                ans=new TreeNode(res[i]);;
                pre=ans;
            }
            else{
                pre->right=new TreeNode(res[i]);
                pre=pre->right;
            }
        }
        return ans;
    }
};