538.Convert the binary search tree to cumulative tree

topic：

"""

Thought：

method one：Travel in the preface Thinking and algorithm

本题中要求我们将每个节点的值修改为原来的节点值加上所有more than the它的节点值之and。这样我们只需要Travel in the preface该二叉searchTree，记录过程中的节点值之and，Not continuously update the node value of the nodes you currently traversed，即可得到topic要求的累加Tree。

Method Two：Morris Traversal Thinking and algorithm

There is a clever way to be online，只占用常数空间来实现中序Traversal。This method is caused by J. H. Morris exist 1979 Annual thesis「Traversing Binary Trees Simply and Cheaply」Proposed for the first time，Because it is called Morris Traversal。

我们以一个简单的Binary tree为例进行说明。假设我们要进行中序Traversal的 Morris Traversal。

Initialization The current node is the root node（current = 1）。
When the current node is not empty，Execute the following steps：
1. The left node of the current node is not empty。We find the front -drive node of the current node，也就是左子Tree中的最右节点。exist这个例子中，The front -drive node is the node5。
2. The right node of the front -drive node is empty，Point your right node to the current node（5 -> 1）。
3. Move the current node to its left child node（current = 2）。
```
          1
           \
            2
           / \
          4   5
```
1. The left node of the current node is not empty。We find the front -drive node of the current node，也就是左子Tree中的最右节点。exist这个例子中，The front -drive node is the node4。
2. The right node of the front -drive node is empty，Point your right node to the current node（4 -> 2）。
3. Move the current node to its left child node（current = 4）。
```
          1
           \
            2
             \
              4
               \
                5
```
1. The left node of the current node is empty。Output当前节点的值（4）。
2. Move the current node to its right node（current = 5）。
3. The left node of the current node is empty。Output当前节点的值（5）。
4. Move the current node to its right node（current = 2）。
```
          1
           \
            2
             \
              4
```
1. The left node of the current node is empty。Output当前节点的值（2）。
2. Move the current node to its right node（current = 1）。
```
          1
           \
            2
```
1. The left node of the current node is empty。Output当前节点的值（1）。
2. Move the current node to its right node（current = 3）。
```
          1
           \
            2
```
1. The left node of the current node is empty。Output当前节点的值（3）。
2. Move the current node to its right node（current = null）。
The current node is empty，Traversal结束。
According to the above steps，通过修改节点between的指针关系，我们完成了对Binary tree的中序Traversal。

Code：

class Solution:
    def convertBST(self, root: TreeNode) -> TreeNode:
        def dfs(root: TreeNode):
            nonlocal total
            if root:
                dfs(root.right)
                total += root.val
                root.val = total
                dfs(root.left)

        total = 0
        dfs(root)
        return root

class Solution:
    def convertBST(self, root: TreeNode) -> TreeNode:
        # Get the successor node of the given node（中序Traversal中的下一个节点）
        def getSuccessor(node: TreeNode) -> TreeNode:
            succ = node.right
            while succ.left and succ.left != node:
                succ = succ.left
            return succ

        total = 0  # 记录累加的节点值之and
        node = root  # The current node initialization is the root node

        while node:
            if not node.right:  # If the right node of the current node is empty
                total += node.val  # Add the value of the current node to the cumulative value
                node.val = total  # Update the value of the current node to accumulate value
                node = node.left  # Move the current node to its left child node
            else:  # If the right node of the current node is not empty
                succ = getSuccessor(node)  # Get the successor node of the current node
                if not succ.left:  # If the left node of the successor node is empty
                    succ.left = node  # Point the left -node of the successor node to the current node，Establish a clue
                    node = node.right  # Move the current node to its right node
                else:  # If the left node of the successor node is not empty
                    succ.left = None  # Set the left node of the successor node to empty，Remove clues
                    total += node.val  # Add the value of the current node to the cumulative value
                    node.val = total  # Update the value of the current node to accumulate value
                    node = node.left  # Move the current node to its left child node

        return root  # Return to the root node

class Solution:
    def convertBST(self, root: TreeNode) -> TreeNode:
        def convert(node: TreeNode, total: int) -> int:
            if not node:
                return total

            # 递归Traversal右子Tree
            total = convert(node.right, total)

            # Update the node value to accumulate and add value
            total += node.val
            node.val = total

            # 递归Traversal左子Tree
            total = convert(node.left, total)

            return total

        convert(root, 0)
        return root

贡献者

longsizhuo贡献 4 次 · 最近 2026/04/18

这篇文章有帮助吗？

538.Convert the binary search tree to cumulative tree

topic：

Thought：

Code：

贡献者

最近更新

On this page