题目:
“””
给出二叉 搜索 树的根节点,该树的节点值各不相同,请你将其转换为累加树(Greater Sum Tree),使每个节点 node
的新值等于原树中大于或等于 node.val
的值之和。
提醒一下,二叉搜索树满足下列约束条件:
- 节点的左子树仅包含键 小于 节点键的节点。
- 节点的右子树仅包含键 大于 节点键的节点。
- 左右子树也必须是二叉搜索树。
注意:本题和 1038: https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/ 相同
示例 1:
输入:[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]
提示:
- 树中的节点数介于
0
和104
之间。 - 每个节点的值介于
-104
和104
之间。 - 树中的所有值 互不相同 。
- 给定的树为二叉搜索树。
思想:
方法一:反序中序遍历
思路及算法
本题中要求我们将每个节点的值修改为原来的节点值加上所有大于它的节点值之和。这样我们只需要反序中序遍历该二叉搜索树,记录过程中的节点值之和,并不断更新当前遍历到的节点的节点值,即可得到题目要求的累加树。
方法二:Morris 遍历
思路及算法
有一种巧妙的方法可以在线性时间内,只占用常数空间来实现中序遍历。这种方法由 J. H. Morris 在 1979 年的论文「Traversing Binary Trees Simply and Cheaply」中首次提出,因此被称为 Morris 遍历。
我们以一个简单的二叉树为例进行说明。假设我们要进行中序遍历的 Morris 遍历。
1 | 1 |
初始化当前节点为根节点(current = 1)。
当前节点不为空时,执行以下步骤:
当前节点的左子节点不为空。我们找到当前节点的前驱节点,也就是左子树中的最右节点。在这个例子中,前驱节点为节点5。
前驱节点的右子节点为空,将其右子节点指向当前节点(5 -> 1)。
将当前节点移动到其左子节点(current = 2)。
1
2
3
4
51
\
2
/ \
4 5当前节点的左子节点不为空。我们找到当前节点的前驱节点,也就是左子树中的最右节点。在这个例子中,前驱节点为节点4。
前驱节点的右子节点为空,将其右子节点指向当前节点(4 -> 2)。
将当前节点移动到其左子节点(current = 4)。
1
2
3
4
5
6
7
81
\
2
\
4
\
5
当前节点的左子节点为空。输出当前节点的值(4)。
将当前节点移动到其右子节点(current = 5)。
当前节点的左子节点为空。输出当前节点的值(5)。
将当前节点移动到其右子节点(current = 2)。
1
2
3
4
51
\
2
\
4当前节点的左子节点为空。输出当前节点的值(2)。
将当前节点移动到其右子节点(current = 1)。
1
2
31
\
2当前节点的左子节点为空。输出当前节点的值(1)。
将当前节点移动到其右子节点(current = 3)。
1
2
31
\
2当前节点的左子节点为空。输出当前节点的值(3)。
将当前节点移动到其右子节点(current = null)。
当前节点为空,遍历结束。
根据上述步骤,通过修改节点之间的指针关系,我们完成了对二叉树的中序遍历。
代码:
1 | class Solution: |
1 | class Solution: |