LeetCode 897. Searching Trees in Ascending Order

示例 1：

输入：root = [5,3,6,2,4,null,8,1,null,null,null,7,9]
输出：
[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

示例 2：

输入：root = [5,1,7]
输出：[1,null,5,null,7]

提示：

• 树中节点数的取值范围是 [1, 100]
• 0 <= Node.val <= 1000

中序遍历之后生成新的树,题目要求我们返回按照中序遍历的结果改造而成的、only the right node等价二叉搜索树.我们可以进行如下操作：

• 先对输入的二叉搜索树执行中序遍历,将结果保存到一个列表中;

• 然后根据列表中的节点值,创建等价的只含有右节点的二叉搜索树,其过程等价于根据节点值创建一个链表.

• 时间复杂度：$O(n)$,其中 $n$ is the total number of nodes in the binary search tree.
• 空间复杂度：$O(n)$,其中 $n$ is the total number of nodes in the binary search tree.需要长度为 $n$ The list holds the values ​​of all nodes of the binary search tree.

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */
class Solution {
    
public:
    void inorder(TreeNode *node,vector<int> &res) {
    
        if(node==nullptr) return;

        inorder(node->left,res);
        res.push_back(node->val);
        inorder(node->right,res);
    }


    TreeNode* increasingBST(TreeNode* root) {
    
        vector<int> res;
        inorder(root,res);

        TreeNode *dummyNode = new TreeNode(-1);
        TreeNode *currNode = dummyNode;
        for(int value: res) {
    
            currNode->right = new TreeNode(value);
            currNode = currNode->right;
        }

        return dummyNode->right;
    }
};

/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */
func increasingBST(root *TreeNode) *TreeNode {
    
    vals := []int{
    }
    var inorder func(*TreeNode)
    inorder = func(node *TreeNode) {
    
        if node != nil {
    
            inorder(node.Left)
            vals = append(vals, node.Val)
            inorder(node.Right)
        }
    }
    inorder(root)

    dummyNode := &TreeNode{
    }
    curNode := dummyNode
    for _, val := range vals {
    
        curNode.Right = &TreeNode{
    Val: val}
        curNode = curNode.Right
    }
    return dummyNode.Right
}

在中序遍历的过程中改变节点指向.Method 1 needs to traverse the binary search tree once,Then create a new equivalent binary search tree.事实上,It is also possible to traverse the input binary search tree once,In the process of traversing, change the node point to meet the requirements of the problem.

during in-order traversal,It can be achieved by modifying the node pointing.具体地,当我们遍历到一个节点时,把它的左孩子设为空,并将其本身作为上一个遍历到的节点的右孩子.Some imagination is required here.During recursive traversal,Since the call stack of the recursive function holds the reference to the node,Therefore, the above operation can be realized.The slides below demonstrate such a process.

• 时间复杂度：$O(n)$,其中 $n$ is the total number of nodes in the binary search tree.
• 空间复杂度：$O(n)$.The stack space overhead in the recursive process is $O(n)$.

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */
class Solution {
    
public:
    // 尾节点
    TreeNode* tail;

    void dfs(TreeNode* root) {
    
        if (!root) return ;
        dfs(root->left);
        // （1）The next node of the tail node becomes the current node
        // （2）Then turn the tail node into a new node
        tail = tail->right = root;
        // 清空左子树
        root->left = nullptr;
        dfs(root->right);
    }

    TreeNode* increasingBST(TreeNode* root) {
    
        // 创建一个虚拟头节点
        auto dummy = new TreeNode();
        tail = dummy;
        dfs(root);
        return dummy->right;
    }
};

class Solution {
    
private:
    TreeNode *resNode;

public:
    void inorder(TreeNode *node) {
    
        if (node == nullptr) {
    
            return;
        }
        inorder(node->left);

        // 在中序遍历的过程中修改节点指向
        resNode->right = node;
        node->left = nullptr;
        resNode = node;

        inorder(node->right);
    }

    TreeNode *increasingBST(TreeNode *root) {
    
        TreeNode *dummyNode = new TreeNode(-1);
        resNode = dummyNode;
        inorder(root);
        return dummyNode->right;
    }
};

func increasingBST(root *TreeNode) *TreeNode {
    
    dummyNode := &TreeNode{
    }
    resNode := dummyNode

    var inorder func(*TreeNode)
    inorder = func(node *TreeNode) {
    
        if node == nil {
    
            return
        }
        inorder(node.Left)

        // 在中序遍历的过程中修改节点指向
        resNode.Right = node
        node.Left = nil
        resNode = node

        inorder(node.Right)
    }
    inorder(root)

    return dummyNode.Right
}