【LeetCode 二叉树专项】把二叉搜索树转换为累加树（538）
1. 题目
给定一棵二叉搜索树（Binary Search Tree: BST）的根节点 root ，请将其转化为一棵累加树，所谓的累加树和原二叉搜索树在结构上完全一样；不同的是对应位置节点的值不同，即累加树上每个节点的值 node.val 是原二叉搜索树所有大于或等于 node.val 的节点值之和。
需要注意的是，二叉搜索树具有下列性质：
- 任意节点的左子树仅包含
node.val小于此节点的节点； - 任意节点的右子树仅包含
node.val大于此节点的节点； - 左右子树也必须是二叉搜索树。
1.1 示例
- 示例
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
2
2 ：
- 输入：
root = [0, null, 1]- 输出：
[1, null, 1]
- 示例
3
3
3 ：
- 输入：
root = [1, 0, 2]- 输出：
[3, 3, 2]
- 示例
4
4
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 限制
- 树中的节点数介于
0
0
0 和1
0
4
10^4
104 之间； - 每个节点的值介于
−
1
0
4
-10^4
−104 和1
0
4
10^4
104 之间； - 树中的所有值互不相同 ；
- 给定的树为二叉搜索树。
2. 解法一（中序遍历）
2.1 分析
由于给定了二叉搜索树，因此首先考虑中序遍历，使用示例
1
1
1 ，我们先来分别看一下二叉搜索树和累加树中序遍历的结果：
- 二叉搜索树：
bst_inorder = [0, 1, 2, 3, 4, 5, 6, 7, 8]； - 二叉累加树：
gbt_inorder = [36, 36, 35, 33, 30, 26, 21, 15, 8]。
通过观察不难发现： gbt_inorder[i] = sum(bst_inorder[i:]) ，其中： 0 <= i < len(bst_inorder) 。
因此，本体可以通过两次中序遍历来求解，第一次得到二叉搜索树的中序便利序列；第二次填充累加树的各个节点值。
2.2 实现
from collections import deque
from typing import Optional
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class 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 root
def 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 复杂度
-
时间复杂度：
O
(
n
)
O(n)
O(n)，其中n
n
n 是二叉搜索树的节点数。每一个节点被遍历两次； -
空间复杂度：
O
(
n
2
)
O(n^2)
O(n2)，由于self._convert_bst方法被递归调用 n 次，每次都使用了列表的切片操作，而切片操作需要额外的内存空间，所以总的内存空间为n
+
(
n
−
1
)
+
⋯
+
1
n+{(n-1)}+cdots+1
n+(n−1)+⋯+1 。
3. 解法二（反中序遍历）
3.1 分析
实际上，仅使用一次中序遍历也可求解本题，而且还更高效。这里还是使用示例
1
1
1 ，我们再来观察一下二叉搜索树和累加树中序遍历的结果：
- 二叉搜索树：
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 序列，更直观的方式应该是：
gbt_inorder[8] = bst_inorder[8] = 8
gbt_inorder[7] = bst_inorder[8] + bst_inorder[7] = 15
gbt_inorder[6] = bst_inorder[8] + bst_inorder[7] + bst_inorder[6] = 21
......
之所以一开始没有使用上面的方式来求解，原因在于使用二叉树的中序遍历时，获取 bst_inorder 元素的顺序和上述所需的顺序是相反的，即上述希望通过 bst_inorder[8] ， bst_inorder[7] ，
⋯
cdots
⋯ ， bst_inorder[0] 这样的顺序获得元素，实际中序遍历顺序却是 bst_inorder[0] ， bst_inorder[1] ，
⋯
cdots
⋯ ， bst_inorder[8] 这样的顺序。
实际上，想要通过满足上述要求的方式得到 bst_inorder 的元素序列也很简单，只要稍微调整一下中序遍历，即按照 右子树 -> 根节点 -> 左子树 这样的顺序来遍历二叉树搜索树，这种遍历方式这里成为反中序遍历。
3.2 实现
from collections import deque
from typing import Optional
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class 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 root
def 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 复杂度
-
时间复杂度：
O
(
n
)
O(n)
O(n)，其中n
n
n 是二叉搜索树的节点数。每一个节点恰好被遍历一次； -
空间复杂度：
O
(
n
)
O(n)
O(n)，为递归过程中栈的开销，平均情况下为O
(
log
n
)
O(log n)
O(logn) ，最坏情况下树呈现链状，为O
(
n
)
O(n)
O(n)。