121 - 538 把二叉树转换为累加树

Previous118 - 437 路径综合3 Next20 - x的平方根

Last updated 5 years ago

Was this helpful?

121 - 538 把二叉树转换为累加树

题目

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

例如：

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

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

解答

只能想到，先变成数组，然后一个个做判断加上去。。

这人用上了二叉树的定义，一下子就简洁了很多。从右往左深度优先遍历，遍历过的都加上就完事了。因为左边总是小于右边的。

这个人的图：

递归

var convertBST = function(root) {
  if (!root) {
    return root
  }
  let sum = 0
  const dfs = function(node) {
    if (!node) {
      return
    }
    dfs(node.right)
    node.val += sum
    sum = node.val
    dfs(node.left)
    return node
  }
  return dfs(root)
};

Runtime: 84 ms, faster than 78.13% of JavaScript online submissions for Convert BST to Greater Tree.
Memory Usage: 40.2 MB, less than 25.00% of JavaScript online submissions for Convert BST to Greater Tree.

class Solution:
    def __init__(self):
        self.sum = 0

    def convertBST(self, root: TreeNode) -> TreeNode:
        if not root:
            return root
        self.convertBST(root.right)
        self.total += root.val
        root.val = self.total
        self.convertBST(root.left)
        return root

Runtime: 84 ms, faster than 59.94% of Python3 online submissions for Convert BST to Greater Tree.
Memory Usage: 16.3 MB, less than 6.25% of Python3 online submissions for Convert BST to Greater Tree.

func convertBST(root *TreeNode) *TreeNode {
    if root != nil {
        dfs(root, 0)
    }
    return root
}
func dfs(node *TreeNode, sum int) int {
    if node == nil {
        return sum
    }
    sum = dfs(node.Right, sum)
    node.Val += sum
    sum = node.Val
    sum = dfs(node.Left, sum)
    return sum
}

Runtime: 188 ms, faster than 88.55% of Go online submissions for Convert BST to Greater Tree.
Memory Usage: 283.6 MB, less than 100.00% of Go online submissions for Convert BST to Greater Tree.

go好像不能像js和python一样，函数里面套函数，只能拆在外面。

栈

就不能是直接的深度遍历，而是要从最右节点开始遍历，因此要加一个字段。。

class Solution:
    def convertBST(self, root: TreeNode) -> TreeNode:
        if not root:
            return root
        prev = 0
        stack = [(False, root)]
        while stack:
            visited, node = stack.pop()
            if visited:
                node.val += prev
                prev = node.val
            else:
                if node.left:
                    stack.append((False, node.left))
                stack.append((True, node))
                if node.right:
                    stack.append((False, node.right))
        return root

Runtime: 88 ms, faster than 34.49% of Python3 online submissions for Convert BST to Greater Tree.
Memory Usage: 16.4 MB, less than 6.25% of Python3 online submissions for Convert BST to Greater Tree.

var convertBST = function(root) {
  if (!root) {
    return root
  }
  let stack = [
    [false, root]
  ]
  let sum = 0
  while (stack.length > 0) {
    let [visited, node] = stack.pop()
    if (visited) {
      node.val += sum
      sum = node.val
    } else {
      if (node.left) {
        stack.push([false, node.left])
      }
      stack.push([true, node])
      if (node.right) {
        stack.push([false, node.right])
      }
    }
  }
  return root
};

Runtime: 92 ms, faster than 40.63% of JavaScript online submissions for Convert BST to Greater Tree.
Memory Usage: 42.6 MB, less than 25.00% of JavaScript online submissions for Convert BST to Greater Tree.

好像用obj改成key-value这样的结构更好。。但遍历就变得很麻烦，还要用keys和delete来维护。。