Last Updated on 2022-04-17 by Clay
題目
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）重新排列成一組遞增、只有右節點的樹結構，並將其回傳。
解題思路
深度優先搜索解法（DFS）
一種很直覺的方式是使用深度優先搜索法來解題。首先，我們先追尋左節點直到最深處，這會是最小值，接著將其賦值到新樹上；接著回到上一層，先將上一層的值賦予新樹的下一個右節點，再繼續使用 DFS 探索右節點...... 依序這個步驟，就能完成新樹的建立。
深度優先搜索解法（DFS）複雜度
由於我們需要遍歷整顆樹，故時間複雜度為 O(n)。而我們又重新建立了新樹，故空間複雜度同樣為 O(n)。
| Time complexity | O(n) |
| Space complexity | O(n) |
深度優先搜索解法（DFS）C++ 範例程式碼
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void solve(TreeNode* root, TreeNode*& newTree) {
// Base case
if (root == nullptr) return;
// Left
solve(root->left, newTree);
// Assign
newTree->right = new TreeNode();
newTree = newTree->right;
newTree->val = root->val;
// Right
solve(root->right, newTree);
}
TreeNode* increasingBST(TreeNode* root) {
// Init
TreeNode* newTree = new TreeNode();
TreeNode* head = newTree;
// Solve
solve(root, newTree);
return head->right;
}
};深度優先搜索解法（DFS）Python 範例程式碼
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def increasingBST(self, root: TreeNode) -> TreeNode:
# Init
newTree = TreeNode()
head = TreeNode(0, right=newTree)
# DFS
def dfs(root: Optional[TreeNode], newTree: TreeNode) -> TreeNode:
if root is not None:
# Left
newTree = dfs(root.left, newTree)
# Step
newTree.right = TreeNode(root.val)
newTree = newTree.right
# Right
newTree = dfs(root.right, newTree)
return newTree
# Result
newTree = dfs(root, newTree)
return head.right.right