Given a Binary Search Tree (where all nodes on the left child branch are less than the node), and all nodes to the right are greater/equal to the node), transform it into a Greater Sum Tree where each node contains sum of it together with all nodes greater than that node. Example diagram is here:
int sum = 0; public TreeNode replaceBST(TreeNode node) { if(node == null) return null; replaceBST(node.right); int tmp = node.val; node.val = sum; sum += tmp; replaceBST(node.left); return node; }
如果最大的节点的值不被更新为0的话,可以这样:
int sum = 0; boolean changed = false; public TreeNode replaceBST(TreeNode node) { if(node == null) return null; replaceBST(node.right); int tmp = node.val; if(changed) { node.val = sum; sum += tmp; } else { changed = true; sum = node.val; } replaceBST(node.left); return node; }
Reference:
相关推荐
http://blog.csdn.net/xkzju2010/article/details/46399155
Binary Search Tree 利用C++實現 Binary Search Tree
关于最优二叉查找树的开山之作,介绍了最优二叉查找树的概念,以及构造最优二叉查找树的动态规划算法,来自D. E. KNUTH,发表于1971年,亦可从这里下载:...
最小成本二分检索树optimal binary optimal binary
A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties: The left subtree of a node contains only nodes with keys less than the node's key. The right ...
binary search tree program using c language
Binary search tree implementation
Binary search Tree implementation.
Binary Search Tree.cpp
binary search tree in c
CpluPlus code for a Text & command based Binary Search Tree Has a menu and base function. Complete but simple
binary search tree in c
C#,二叉搜索树(Binary Search Tree)的迭代方法与源代码 二叉搜索树(BST,Binary Search Tree)又称二叉查找树或二叉排序树。 一棵二叉搜索树是以二叉树来组织的,可以使用一个链表数据结构来表示,其中每一个...
是Binary Search Tree code 二叉检索树的代码,实现了插入,删除,检索,遍历,包括先序遍历,中序遍历,后序遍历
习题选讲-Complete Binary Search Tree.pptx
binary_tree
A binary search finds the median element in a list, compares its value to the one you are searching for, and determines if it’s greater than, less than, or equal to the one you want. A guess that ...
c++ 二分搜索树 二分查找树 binary search tree BST
Build an optimal binary search tree using dynamic programming.
Binary search tree code written in c language