897. Increasing Order Search Tree
Given 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 1 right child.
Example 1: Input: [5,3,6,2,4,null,8,1,null,null,null,7,9] 5 / \ 3 6 / \ \ 2 4 8 / / \ 1 7 9 Output: [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
Constraints:
- The number of nodes in the given tree will be between
1
and100
. - Each node will have a unique integer value from
0
to1000
.
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { TreeNode result; TreeNode curr; public TreeNode increasingBST(TreeNode root) { makeFlatInOrder(root); return result; } public void makeFlatInOrder(TreeNode node){ if(node == null){ return; } makeFlatInOrder(node.left); if(curr == null){ result = new TreeNode(node.val); curr = result; }else{ curr.right = new TreeNode(node.val); curr = curr.right; } makeFlatInOrder(node.right); } }
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public TreeNode increasingBST(TreeNode root) { List<TreeNode> list = new ArrayList<>(); inOrder(root, list); TreeNode node = new TreeNode(-1); TreeNode curr = node; for(TreeNode item : list){ curr.right = new TreeNode(item.val); curr = curr.right; } return node.right; } public void inOrder(TreeNode node, List<TreeNode> list){ if(node == null){ return; } inOrder(node.left, list); list.add(node); inOrder(node.right, list); } }
[문제] https://leetcode.com/problems/increasing-order-search-tree/
-
720. Longest Word in Dictionary
-
225. Implement Stack using Queues
-
56. Merge Intervals
-
844. Backspace String Compare
-
222. Count Complete Tree Nodes
-
697. Degree of an Array
-
605. Can Place Flowers
-
724. Find Pivot Index
-
448. Find All Numbers Disappeared in an Array
-
628. Maximum Product of Three Numbers
-
532. K-diff Pairs in an Array
-
897. Increasing Order Search Tree
-
872. Leaf-Similar Trees
-
876. Middle of the Linked List
-
203. Remove Linked List Elements
-
997. Find the Town Judge
-
270. Closest Binary Search Tree Value
-
687. Longest Univalue Path
-
783. Minimum Distance Between BST Nodes
-
235. Lowest Common Ancestor of a Binary Search Tree