文章目錄

• • 1. 題目
  • • 1.1 示例
    • 1.2 說明
    • 1.3 限制
  • 2. 解法一（中序遍歷）
  • • 2.1 分析
    • 2.2 實現(xiàn)
    • 2.3 復(fù)雜度
  • 3. 解法二（反中序遍歷）
  • • 3.1 分析
    • 3.2 實現(xiàn)
    • 3.3 復(fù)雜度
  • 4. 解法三（Morris 遍歷）

1. 題目

給定一棵二叉搜索樹（Binary Search Tree: BST）的根節(jié)點 root ，請將其轉(zhuǎn)化為一棵累加樹，所謂的累加樹和原二叉搜索樹在結(jié)構(gòu)上完全一樣；不同的是對應(yīng)位置節(jié)點的值不同，即累加樹上每個節(jié)點的值 node.val 是原二叉搜索樹所有大于或等于 node.val 的節(jié)點值之和。

需要注意的是，二叉搜索樹具有下列性質(zhì)：

• 任意節(jié)點的左子樹僅包含 node.val 小于此節(jié)點的節(jié)點；
• 任意節(jié)點的右子樹僅包含 node.val 大于此節(jié)點的節(jié)點；
• 左右子樹也必須是二叉搜索樹。

1.1 示例

• 示例 $1$ ：

• 輸入： root = [4, 1, 6, 0, 2, 5, 7, null, null, null, 3, null, null, null, 8]
• 輸出： [30, 36, 21, 36, 35, 26, 15, null, null, null, 33, null, null, null, 8]

• 示例 $2$ ：

• 輸入： root = [0, null, 1]
• 輸出： [1, null, 1]

• 示例 $3$ ：

• 輸入： root = [1, 0, 2]
• 輸出： [3, 3, 2]

• 示例 $4$ ：

• 輸入： root = [3, 2, 4, 1]
• 輸出： [7, 9, 4, 10]

1.2 說明

• 來源： 力扣（LeetCode）
• 鏈接： https://leetcode-cn.com/problems/convert-bst-to-greater-tree

1.3 限制

• 樹中的節(jié)點數(shù)介于 $0$ 和 $10^4$ 之間；
• 每個節(jié)點的值介于 $?10^4$ 和 $10^4$ 之間；
• 樹中的所有值互不相同 ；
• 給定的樹為二叉搜索樹。

2. 解法一（中序遍歷）

2.1 分析

由于給定了二叉搜索樹，因此首先考慮中序遍歷，使用示例 $1$ ，我們先來分別看一下二叉搜索樹和累加樹中序遍歷的結(jié)果：

• 二叉搜索樹： bst_inorder = [0, 1, 2, 3, 4, 5, 6, 7, 8] ；
• 二叉累加樹： gbt_inorder = [36, 36, 35, 33, 30, 26, 21, 15, 8] 。

通過觀察不難發(fā)現(xiàn)： gbt_inorder[i] = sum(bst_inorder[i:]) ，其中： 0 <= i < len(bst_inorder) 。

因此，本體可以通過兩次中序遍歷來求解，第一次得到二叉搜索樹的中序便利序列；第二次填充累加樹的各個節(jié)點值。

2.2 實現(xiàn)

from collections import dequefrom typing import Optionalclass TreeNode:    def __init__(self, val=0, left=None, right=None):        self.val = val        self.left = left        self.right = rightclass Solution:    def __init__(self):        self._tree = []        self._counter = 0    def _inorder_traverse(self, root: Optional[TreeNode]):        if not root:            return        self._inorder_traverse(root.left)        self._tree.append(root.val)        self._inorder_traverse(root.right)    def _convert_bst(self, root: Optional[TreeNode]) -> Optional[TreeNode]:        if not root:            return        self._convert_bst(root.left)        root.val = sum(self._tree[self._counter:])        self._counter += 1        self._convert_bst(root.right)    def convert_bst(self, root: Optional[TreeNode]) -> Optional[TreeNode]:        self._inorder_traverse(root)        self._convert_bst(root)        return rootdef main():    node9 = TreeNode(8)    node8 = TreeNode(3)    node7 = TreeNode(7, right=node9)    node6 = TreeNode(5)    node5 = TreeNode(2, right=node8)    node4 = TreeNode(0)    node3 = TreeNode(6, left=node6, right=node7)    node2 = TreeNode(1, left=node4, right=node5)    node1 = TreeNode(4, left=node2, right=node3)    root = node1    sln = Solution()    sln.convert_bst(root)    tree = []    visiting = deque([root])    while visiting:        node = visiting.popleft()        if node:            tree.append(node.val)            visiting.append(node.left)            visiting.append(node.right)        else:            tree.append(None)    while True:        if not tree[-1]:            tree.pop()        else:            break    print(tree)  # [30, 36, 21, 36, 35, 26, 15, None, None, None, 33, None, None, None, 8]if __name__ == "__main__":    main()

2.3 復(fù)雜度

• 時間復(fù)雜度： $O(n)$，其中 $n$ 是二叉搜索樹的節(jié)點數(shù)。每一個節(jié)點被遍歷兩次；
• 空間復(fù)雜度： $O(n^2)$，由于 self._convert_bst 方法被遞歸調(diào)用 n 次，每次都使用了列表的切片操作，而切片操作需要額外的內(nèi)存空間，所以總的內(nèi)存空間為 $n+(n?1)+?+1$ 。

3. 解法二（反中序遍歷）

3.1 分析

實際上，僅使用一次中序遍歷也可求解本題，而且還更高效。這里還是使用示例 $1$ ，我們再來觀察一下二叉搜索樹和累加樹中序遍歷的結(jié)果：

• 二叉搜索樹： bst_inorder = [0, 1, 2, 3, 4, 5, 6, 7, 8] ；
• 二叉累加樹： gbt_inorder = [36, 36, 35, 33, 30, 26, 21, 15, 8] 。

實際上，如希望通過 bst_inorder 序列來得到 gbt_inorder 序列，更直觀的方式應(yīng)該是：

gbt_inorder[8] = bst_inorder[8] = 8gbt_inorder[7] = bst_inorder[8] + bst_inorder[7] = 15gbt_inorder[6] = bst_inorder[8] + bst_inorder[7] + bst_inorder[6] = 21......

之所以一開始沒有使用上面的方式來求解，原因在于使用二叉樹的中序遍歷時，獲取 bst_inorder 元素的順序和上述所需的順序是相反的，即上述希望通過 bst_inorder[8] ， bst_inorder[7] ， $?$ ， bst_inorder[0] 這樣的順序獲得元素，實際中序遍歷順序卻是 bst_inorder[0] ， bst_inorder[1] ， $?$ ， bst_inorder[8] 這樣的順序。

實際上，想要通過滿足上述要求的方式得到 bst_inorder 的元素序列也很簡單，只要稍微調(diào)整一下中序遍歷，即按照 右子樹 -> 根節(jié)點 -> 左子樹 這樣的順序來遍歷二叉樹搜索樹，這種遍歷方式這里成為反中序遍歷。

3.2 實現(xiàn)

from collections import dequefrom typing import Optionalclass TreeNode:    def __init__(self, val=0, left=None, right=None):        self.val = val        self.left = left        self.right = rightclass Solution:    def __init__(self):        self._total = 0    def _reverse_inorder(self, root: Optional[TreeNode]):        if not root:            return        self._reverse_inorder(root.right)        self._total += root.val        root.val = self._total        self._reverse_inorder(root.left)    def convert_bst(self, root: Optional[TreeNode]) -> Optional[TreeNode]:        self._reverse_inorder(root)        return rootdef main():    node9 = TreeNode(8)    node8 = TreeNode(3)    node7 = TreeNode(7, right=node9)    node6 = TreeNode(5)    node5 = TreeNode(2, right=node8)    node4 = TreeNode(0)    node3 = TreeNode(6, left=node6, right=node7)    node2 = TreeNode(1, left=node4, right=node5)    node1 = TreeNode(4, left=node2, right=node3)    root = node1    sln = Solution()    sln.convert_bst(root)    tree = []    visiting = deque([root])    while visiting:        node = visiting.popleft()        if node:            tree.append(node.val)            visiting.append(node.left)            visiting.append(node.right)        else:            tree.append(None)    while True:        if not tree[-1]:            tree.pop()        else:            break    print(tree)  # [30, 36, 21, 36, 35, 26, 15, None, None, None, 33, None, None, None, 8]if __name__ == "__main__":    main()

3.3 復(fù)雜度

• 時間復(fù)雜度： $O(n)$，其中 $n$ 是二叉搜索樹的節(jié)點數(shù)。每一個節(jié)點恰好被遍歷一次；
• 空間復(fù)雜度： $O(n)$，為遞歸過程中棧的開銷，平均情況下為 $O(\log n)$ ，最壞情況下樹呈現(xiàn)鏈狀，為 $O(n)$。

4. 解法三（Morris 遍歷）

• 作者： LeetCode-Solution