897. incremental sequential search tree

Preface

C++ It's a high-level programming language , from C Language expansion and upgrading , As early as 1979 By Benjani · Strauss LUP is AT&T Developed by Bell studio .
C++ Both can be carried out C Process programming of language , It can also be used for object-based programming characterized by abstract data types , It can also carry out object-oriented programming characterized by inheritance and polymorphism .C++ Good at object-oriented programming at the same time , You can also do process based programming .
C++ Have the practical characteristics of computer operation , At the same time, it is also committed to improving the programming quality of large-scale programs and the problem description ability of programming languages .

Java Is an object-oriented programming language , Not only absorbed C++ The advantages of language , It's abandoned C++ The incomprehensible inheritance in 、 Concepts such as pointer , therefore Java Language has two characteristics: powerful and easy to use .Java As the representative of static object-oriented programming language , Excellent implementation of object-oriented theory , Allow programmers to do complex programming in an elegant way of thinking .
Java It's simple 、 object-oriented 、 Distributed 、 Robustness, 、 Security 、 Platform independence and portability 、 Multithreading 、 Dynamic and so on .Java Can write desktop applications 、Web Applications 、 Distributed system and embedded system applications, etc .

Python By Guido of the Dutch Society for mathematical and computer science research · Van rosum On 1990 It was designed in the early 's , As a course called ABC A substitute for language .Python Provides efficient advanced data structure , It's also a simple and effective way of object-oriented programming .Python Syntax and dynamic types , And the nature of interpretative language , Make it a programming language for scripting and rapid application development on most platforms , With the continuous update of the version and the addition of new language features , Gradually used for independent 、 Development of large projects .
Python The interpreter is easy to extend , have access to C Language or C++（ Or something else can be done through C Calling language ） Expand new functions and data types .Python It can also be used as an extensible programming language in customizable software .Python Rich library of standards , Provides source code or machine code for each major system platform .
2021 year 10 month , Compiler for language popularity index Tiobe take Python Crowned the most popular programming language ,20 Put it in... For the first time in years Java、C and JavaScript above .

describe

Give you a binary search tree root , Would you please Traverse in middle order Rearrange it into an incremental sequential search tree , Make the leftmost node in the tree the root node of the tree , And each node has no left child , There is only one right child node .

Example 1：

Input ：root = [5,3,6,2,4,null,8,1,null,null,null,7,9]
Output ：[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

Example 2：

Input ：root = [5,1,7]
Output ：[1,null,5,null,7]

Tips ：

    The range of the number of nodes in the tree is [1, 100]
    0 <= Node.val <= 1000

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/increasing-order-search-tree
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Method 1 ： Generate a new tree after traversing the middle order

Algorithm

The title requires us to return the result of traversal in middle order 、 An equivalent binary search tree with only right nodes . We can do the following ：

    First, the binary search tree is traversed in middle order , Save the results to a list ;

    Then according to the node values in the list , Create an equivalent binary search tree with only right nodes , The process is equivalent to creating a linked list according to the node values .

author ：LeetCode-Solution
link ：https://leetcode.cn/problems/increasing-order-search-tree/solution/di-zeng-shun-xu-cha-zhao-shu-by-leetcode-dfrr/
source ： Power button （LeetCode）
The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source .

class Solution {
    public TreeNode increasingBST(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        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;
    }

    public void inorder(TreeNode node, List<Integer> res) {
        if (node == null) {
            return;
        }
        inorder(node.left, res);
        res.add(node.val);
        inorder(node.right, res);
    }
}


 author ：LeetCode-Solution
 link ：https://leetcode.cn/problems/increasing-order-search-tree/solution/di-zeng-shun-xu-cha-zhao-shu-by-leetcode-dfrr/
 source ： Power button （LeetCode）
 The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source .