[算法]二叉查找树

二叉查找树（Binary Search Tree，BST），也叫二叉搜索树，排序二叉树，指一棵空树或具有下列性质的二叉树：

若任意节点的左子树不为空，则左子树上所有节点的值均小于它的根节点的值
若任意节点的右子树不为空，则右子树上所有节点的值均大于它的根节点的值
任意节点的左，右子树也分别为二叉查找树
没有键值相等的点

实例

leetcode 538 convert-bst-to-greater-tree

把 bst 转为累加树，采用反向中序遍历求解

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


var convertBST = function(root) {
  var stack = [];
  var currentNode = root;
  var sum = 0;
  while (currentNode || stack.length > 0) {
    if (currentNode) {
      stack.push(currentNode);
      currentNode = currentNode.right;
    } else {
      var node = stack.pop();
      sum += node.val;
      node.val = sum;
      currentNode = node.left;
    }
  }
  return root;
};