538.Convert the binary search tree to cumulative tree

2024-01-01

字数统计: 1.2k字 | 阅读时长: 6min

topic：

“””

Give two forks search Root node，The node value of the tree is different，Please convert it to a cumulative tree（Greater Sum Tree），Make each node node The new value of the original tree is greater than or equal to the original tree node.val The sum of the value。

remind，二叉searchTree满足下列约束条件：

The left tree of the node contains only the key Less than Node node node。
The right tree of the node contains only the key more than the Node node node。
左右子Tree也必须是二叉searchTree。

Notice：This question 1038: https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/ same

Exemplary example 1：

enter：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
Output：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

Exemplary example 2：

enter：root = [0,null,1]
Output：[1,null,1]

Exemplary example 3：

enter：root = [1,0,2]
Output：[3,3,2]

Exemplary example 4：

enter：root = [3,2,4,1]
Output：[7,9,4,10]

hint：

The number of nodes in the tree is in 0 and 10⁴between。
The value of each node -10⁴ and 10⁴ between。
All the values in the tree 互不same 。
给定的Tree为二叉searchTree。

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
  3
  4
  5
  1
  \
  2
  / \
  4 5
4. 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。
5. The right node of the front -drive node is empty，Point your right node to the current node（4 -> 2）。
6. Move the current node to its left child node（current = 4）。
  1
  2
  3
  4
  5
  6
  7
  8
  1
  \
  2
  \
  4
  \
  5
7. The left node of the current node is empty。Output当前节点的值（4）。
8. Move the current node to its right node（current = 5）。
9. The left node of the current node is empty。Output当前节点的值（5）。
10. Move the current node to its right node（current = 2）。
  1
  2
  3
  4
  5
  1
  \
  2
  \
  4
11. The left node of the current node is empty。Output当前节点的值（2）。
12. Move the current node to its right node（current = 1）。
  1
  2
  3
  1
  \
  2
13. The left node of the current node is empty。Output当前节点的值（1）。
14. Move the current node to its right node（current = 3）。
  1
  2
  3
  1
  \
  2
15. The left node of the current node is empty。Output当前节点的值（3）。
16. 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：

中序Traversal

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

MorrisTraversal

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