【一天一大 lee】 把二叉搜索树转换为累加树 (难度:简单)-Day20200921

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

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

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var convertBST = function(root) {
  let sum = 0
  function dfs(node) {
    if (node == null) return node
    dfs(node.right)
    sum = sum + node.val
    node.val = sum
    dfs(node.left)
  }
  dfs(root)
  return root
}

var convertBST = function(root) {
  let sum = 0
  function getMorris(node) {
    next = node.right
    while (next.left != null && next.left != node) {
      next = next.left
    }
    return next
  }
  let node = root
  while (node != null) {
    if (node.right == null) {
      sum += node.val
      node.val = sum
      node = node.left
    } else {
      mrris = getMorris(node)
      if (mrris.left == null) {
        mrris.left = node
        node = node.right
      } else {
        mrris.left = null
        sum += node.val
        node.val = sum
        node = node.left
      }
    }
  }
  return root
}