把二叉搜索树转换为累加树

Convert BST to Greater Tree ⭐️

LeetCode每日一题 2020.09.21

给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。

Example:

输入: 原始二叉搜索树:
              5
            /   \
           2     13

输出: 转换为累加树:
             18
            /   \
          20     13

题目大意

按照题目大意根节点 5，整个树中大于根节点的有 13，所以当前节点累加后为 18，以此类推左子树为 2+5+13=20，右子树根节点为 13。

解题思路

方式一: 反中序遍历

思路

反中序遍历该二叉搜索树，记录过程中的节点值之和，并不断更新当前遍历到的节点的节点值，即可得到题目要求的累加树。

代码

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func convertBST(root *TreeNode) *TreeNode {
    sum := 0
    var dfs func(*TreeNode)
    dfs = func(node *TreeNode) {
        if node != nil {
            dfs(node.Right)
            sum += node.Val
            node.Val = sum
            dfs(node.Left)
        }
    }
    dfs(root)
    return root
}

复杂度分析

时间复杂度: $O(n)$ , 其中 n 是二叉树中的节点个数。
空间复杂度: $O(n)$ , 为递归过程中栈的开销，平均情况下为 $O(logn)$ ，最坏情况下树呈现链状，为 $O(n)$ 。

方式二: Morris 反中序遍历 (思路来自官方题解)

思路

如果当前节点的右孩子为空，则输出当前节点并将其左孩子作为当前节点。
如果当前节点的右孩子不为空，在当前节点的右子树中找到当前节点在中序遍历下的后继节点。
- a) 如果后继节点的左孩子为空，将它的左孩子设置为当前节点。当前节点更新为当前节点的右孩子。
- b) 如果后驱节点的左孩子为当前节点，将它的左孩子重新设为空（恢复树的形状）。输出当前节点。当前节点更新为当前节点的左孩子。
重复以上步骤直到当前节点为空。

二叉搜索树特性

若任意结点的左子树不空，则左子树上所有结点的值均不大于它的根结点的值。
若任意结点的右子树不空，则右子树上所有结点的值均不小于它的根结点的值。
任意结点的左、右子树也分别为二叉搜索树。

提示

Morris方法用到了线索二叉树（threaded binary tree）的概念。在Morris方法中不需要为每个节点额外分配指针指向其前驱（predecessor）和后继节点（successor），只需要利用叶子节点中的左右空指针指向某种顺序遍历下的前驱节点或后继节点就可以了。此题中利用二叉搜索树的特性使用反中序遍历

代码

func convertBST(root *TreeNode) *TreeNode {
    sum := 0
    node := root
    for node != nil {
        if node.Right == nil {
            sum += node.Val
            node.Val = sum
            node = node.Left
        } else {
            successor := node.Right
            for successor.Left != nil && successor.Left != node {
                successor = successor.Left
            }
                // 2.a)
            if successor.Left == nil {
                successor.Left = node
                node = node.Right
            } else {
                // 2.b)
                successor.Left = nil
                sum += node.Val
                node.Val = sum
                node = node.Left
            }
        }
    }
    return root
}