LeetCode 솔루션

897. Increasing Order Search Tree

Jack 쪽지보내기 메일보내기 자기소개 아이디로 검색 전체게시물 작성
작성일 2022.04.17 00:42

7,211 조회
2 댓글
0 추천
0 비추천
목록 게시글 쓰기

[ Leetcode 시즌 3 ] 4월 16일 문제 입니다.

[ Easy ] 897. Increasing Order Search Tree

897. Increasing Order Search Tree

Easy

2668609Add to ListShare

Given the root of a binary search tree, rearrange the tree in in-order so that the leftmost node in the tree is now the root of the tree, and every node has no left child and only one right child.

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]

Constraints:

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

Companies: Facebook

Related Topics: Stack, Tree, Depth-First Search, Binary Search Tree, Binary Tree

#leetcode, #문제풀이, #시즌3, #easy, #facebook, #Stack, #Tree, #Depth-First Search, #Binary Search Tree, #Binary Tree

링크

https://leetcode.com/problems/increasing-order-search-tree/ 1238 회 연결

익명
작성일 2022.04.17 13:03

class Solution:
    def increasingBST(self, root: TreeNode) -> TreeNode:
        self.ans = TreeNode()
        self.head = self.ans
        def rf(root):
            if not root:
                return None
            rf(root.left)
            self.head.right = TreeNode(root.val)
            self.head = self.head.right
            rf(root.right)
        rf(root)
        return self.ans.right

익명
작성일 2022.04.18 11:12

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Increasing Order Search Tree.
Memory Usage: 7.7 MB, less than 78.07% of C++ online submissions for Increasing Order Search Tree.

class Solution {
public:
    TreeNode* increasingBST(TreeNode* root) {
        //Stopper
        if(!root){
            return nullptr;
        }
        
        //Recursively connecting left and right nodes
        TreeNode* p_tmp=nullptr;
        TreeNode* p_right=increasingBST(root->right);
        TreeNode* p_left=increasingBST(root->left);

        
        //Connect to make ans chain
        root->right = p_right;
        root->left = nullptr;
        
        //No more left node
        if(!p_left)
            return root;
        
        //Find the rightmost node
        p_tmp=p_left;        
        while(p_tmp->right!=nullptr){
            p_tmp=p_tmp->right;
        }
    
        //Connect the rightmost node
        p_tmp->right=root;
    
        //Returning the leftmost of each chain
        return p_left;
    }
};

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Increasing Order Search Tree.
Memory Usage: 7.7 MB, less than 78.07% of C++ online submissions for Increasing Order Search Tree.
[code=C++]class Solution {
public:
    TreeNode* increasingBST(TreeNode* root) {
        //Stopper
        if(!root){
            return nullptr;
        }
        
        //Recursively connecting left and right nodes
        TreeNode* p_tmp=nullptr;
        TreeNode* p_right=increasingBST(root->right);
        TreeNode* p_left=increasingBST(root->left);

//Connect to make ans chain
        root->right = p_right;
        root->left = nullptr;
        
        //No more left node
        if(!p_left)
            return root;
        
        //Find the rightmost node
        p_tmp=p_left;        
        while(p_tmp->right!=nullptr){
            p_tmp=p_tmp->right;
        }
    
        //Connect the rightmost node
        p_tmp->right=root;
    
        //Returning the leftmost of each chain
        return p_left;
    }
};[/code]