Increasing Order Search Tree (M)
題目
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
題意
將一個BST按照順序變成一直鏈，
思路
簡單的可以用中序遍歷實作，或者用類似Morris遍歷的方法也可以，
代碼實作
Java
中序遍歷
class Solution {
public TreeNode increasingBST(TreeNode root) {
List<TreeNode> list = new ArrayList<>();
inorder(root, list);
TreeNode dummy = new TreeNode();
TreeNode p = dummy;
for (TreeNode node : list) {
p.right = node;
p = node;
}
return dummy.right;
}
private void inorder(TreeNode root, List<TreeNode> list) {
if (root == null) {
return;
}
inorder(root.left, list);
list.add(root);
root.left = null;
inorder(root.right, list);
}
}
Morris
class Solution {
public TreeNode increasingBST(TreeNode root) {
TreeNode newRoot = root;
while (newRoot != null && newRoot.left != null) {
newRoot = newRoot.left;
}
while (root != null) {
if (root.left != null) {
TreeNode rightMost = root.left;
while (rightMost.right != null) {
rightMost = rightMost.right;
}
rightMost.right = root;
root = root.left;
rightMost.right.left = null;
} else if (root.right != null && root.right.left != null) {
root.right = increasingBST(root.right);
root = root.right;
} else {
root = root.right;
}
}
return newRoot;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/229714.html
標籤：其他