엔지니어 게시판
LeetCode 솔루션 분류

897. Increasing Order Search Tree

컨텐츠 정보

본문

[ 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

관련자료

댓글 2

9dea0936님의 댓글

  • 익명
  • 작성일
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

bobkim님의 댓글

  • 익명
  • 작성일
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;
    }
};
전체 29 / 1 페이지
번호
제목
이름

최근글


인기글


새댓글


Stats


알림 0