Leetcode 刷題日記
2021.2.20
題目鏈接：
https://leetcode-cn.com/problems/increasing-order-search-tree/
問題描述：
按遞增順序把二叉查找樹進行重新排列
解答：
分治演算法（本質是中序遍歷的遞回實作）
代碼：
class Solution {
public TreeNode increasingBST(TreeNode root) {
TreeNode newRoot = root;
while(newRoot.left != null) newRoot = newRoot.left;
//get the new root of the tree
if(root.left != null) {
operationOnLeft(root.left).right = root;
root.left = null;
}
if(root.right != null) {
TreeNode[] right = operationOnRight(root.right);
root.right = right[0];
}
return newRoot;
}
public TreeNode operationOnLeft(TreeNode root){
if(root.left != null){
operationOnLeft(root.left).right = root;
root.left = null;
}
if(root.right != null){
TreeNode[] right = operationOnRight(root.right);
root.right = right[0];
return right[1];
}
return root;
}
public TreeNode[] operationOnRight(TreeNode root){
TreeNode[] result = new TreeNode[2];
if(root.left != null){
TreeNode[] left = operationOnRight(root.left);
left[1].right = root;
root.left = null;
result[0] = left[0];
}else{
result[0] = root;
}
if(root.right != null){
TreeNode[] right = operationOnRight(root.right);
root.right = right[0];
result[1] = right[1];
}else{
result[1] = root;
}
return result;
}
}
分析：
時間復雜度：O(n)
空間復雜度：O(n)
運行結果：
評注:
分治演算法擁有較快的運行速度，但是記憶體消耗量較大，為了解決這個問題，筆者嘗試了手動釋放記憶體的辦法，對于每一個在遞回函式中new出來的物件，筆者在其使用完畢后都將其參考賦為null，以加快jvm對它們的回收，記憶體消耗明顯減少，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/262188.html
標籤：java
上一篇：深入理解java的 抽象類和介面