c/c++ leetcode 897. 递增顺序查找树

题目描述

难度简单92

给你一个树，请你 按中序遍历 重新排列树，使树中最左边的结点现在是树的根，并且每个结点没有左子结点，只有一个右子结点。

示例：

输入：[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 范围内的唯一整数值。

官方题解:https://leetcode-cn.com/problems/increasing-order-search-tree/solution/di-zeng-shun-xu-cha-zhao-shu-by-leetcode/

解法一: 中序遍历 + 构建一个新的树(链表)

class Solution {public:    vector
   
     temp;    TreeNode* increasingBST(TreeNode* root) {        if (!root) return root;        helper(root);        TreeNode newHead;        TreeNode * p = &newHead;        int i = 0;                while (i < temp.size()) {            TreeNode * node = new TreeNode(temp[i++]);            p -> right = node;            p = p -> right;        }                return newHead.right;    }    void helper(TreeNode* root){        if (!root) return;                helper(root -> left);        //节点数据从小到到大进入temp容器中        temp.push_back(root -> val);        helper(root -> right);    }};

时空复杂度分析:

时间复杂度: O(N) ; N为节点个数;

空间复杂度: O(N); 需要把树中的节点数据保存在vector容器中;

解法二: 中序遍历 + 更改树的连接方式

class Solution {public:       TreeNode* increasingBST(TreeNode* root) {        if (!root) return root;        TreeNode ans(0); //哨兵        TreeNode* curr = &ans;        helper(root,curr);        return ans.right;    }	    //curr指针的引用相当于二级指针    void helper(TreeNode* root ,TreeNode*& cur) {        if (!root) return;        helper(root -> left,cur);        cur -> right = root;        cur = cur -> right;        root -> left = NULL;        helper(root -> right,cur);    }};