怎么做网站加盟/互联网营销行业前景

文章目录

• • 1. 题目
  • • 1.1 示例
    • 1.2 说明
    • 1.3 限制
  • 2. 解法一（中序遍历）
  • • 2.1 分析
    • 2.2 实现
    • 2.3 复杂度
  • 3. 解法二（反中序遍历）
  • • 3.1 分析
    • 3.2 实现
    • 3.3 复杂度
  • 4. 解法三（Morris 遍历）

1. 题目

给定一棵二叉搜索树（Binary Search Tree: BST）的根节点 root ，请将其转化为一棵累加树，所谓的累加树和原二叉搜索树在结构上完全一样；不同的是对应位置节点的值不同，即累加树上每个节点的值 node.val 是原二叉搜索树所有大于或等于 node.val 的节点值之和。

需要注意的是，二叉搜索树具有下列性质：

• 任意节点的左子树仅包含 node.val 小于此节点的节点；
• 任意节点的右子树仅包含 node.val 大于此节点的节点；
• 左右子树也必须是二叉搜索树。

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 限制

• 树中的节点数介于 $0$ 和 $10^4$ 之间；
• 每个节点的值介于 $-10^4$ 和 $10^4$ 之间；
• 树中的所有值互不相同 ；
• 给定的树为二叉搜索树。

2. 解法一（中序遍历）

2.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 Optionalclass TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightclass Solution:def __init__(self):self._tree = []self._counter = 0def _inorder_traverse(self, root: Optional[TreeNode]):if not root:returnself._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:returnself._convert_bst(root.left)root.val = sum(self._tree[self._counter:])self._counter += 1self._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 = node1sln = 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:breakprint(tree)  # [30, 36, 21, 36, 35, 26, 15, None, None, None, 33, None, None, None, 8]if __name__ == '__main__':main()

2.3 复杂度

• 时间复杂度： $O(n)$，其中 $n$ 是二叉搜索树的节点数。每一个节点被遍历两次；
• 空间复杂度： $O(n^2)$，由于 self._convert_bst 方法被递归调用 n 次，每次都使用了列表的切片操作，而切片操作需要额外的内存空间，所以总的内存空间为 $n+(n-1)+\cdots +1$ 。

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

3.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 Optionalclass TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightclass Solution:def __init__(self):self._total = 0def _reverse_inorder(self, root: Optional[TreeNode]):if not root:returnself._reverse_inorder(root.right)self._total += root.valroot.val = self._totalself._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 = node1sln = 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:breakprint(tree)  # [30, 36, 21, 36, 35, 26, 15, None, None, None, 33, None, None, None, 8]if __name__ == '__main__':main()

3.3 复杂度

• 时间复杂度： $O(n)$，其中 $n$ 是二叉搜索树的节点数。每一个节点恰好被遍历一次；
• 空间复杂度： $O(n)$，为递归过程中栈的开销，平均情况下为 $O(\log n)$ ，最坏情况下树呈现链状，为 $O(n)$。

4. 解法三（Morris 遍历）

• 作者： LeetCode-Solution