LeetCode如何把二叉搜索树转换为累加树
一、什么是二叉搜索树
二叉搜索树(Binary Search Tree),又称二叉查找树或二叉排序树,它是一种特殊的二叉树,它具有以下性质:
- 1、若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值;
- 2、若任意节点的右子树不空,则右子树上所有节点的值均大于它的根节点的值;
- 3、任意节点的左、右子树也分别为二叉搜索树;
- 4、没有键值相等的节点。
二、什么是累加树
累加树(Binary Tree to Greater Sum Tree)是一种特殊的二叉树,它具有以下性质:
- 1、若任意节点的左子树不空,则根节点的值等于它的左子树上所有节点的值的累加和;
- 2、若任意节点的右子树不空,则根节点的值等于它的右子树上所有节点的值的累加和;
- 3、任意节点的左、右子树也分别为累加树;
- 4、没有键值相等的节点。
三、LeetCode如何把二叉搜索树转换为累加树
LeetCode提供了一种比较有效的方法来将二叉搜索树转换为累加树,这种方法的思想是:从树的最右节点开始,每个节点的值都是它的右子树上所有节点的值的累加和,然后再从树的最右节点开始,每个节点的值都是它的左子树上所有节点的值的累加和。
下面是LeetCode实现的一个示例代码:
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {TreeNode}
*/
var bstToGst = function(root) {
let sum = 0;
// 从右节点开始,每个节点的值都是它的右子树上所有节点的值的累加和
const traverse = (node) => {
if (node === null) return;
traverse(node.right);
sum += node.val;
node.val = sum;
traverse(node.left);
}
// 从右节点开始,每个节点的值都是它的左子树上所有节点的值的累加和
traverse(root);
return root;
};
以上代码实现了将二叉搜索树转换为累加树的功能,从右节点开始,每个节点的值都是它的右子树上所有节点的值的累加和,然后再从右节点开始,每个节点的值都是它的左子树上所有节点的值的累加和,最终实现了将二叉搜索树转换为累加树的目的。
上一篇
如何进行vue入门环境搭建及运行 下一篇
Netty零拷贝是什么意思 猜您想看
-
python3 str或bytes怎么实现转换函数
Python3...
2023年05月26日 -
RocketMQ中Connection命令怎么用
1. Conn...
2023年05月26日 -
java中怎么实现一个压缩包工具类
1、实现压缩包...
2023年05月26日 -
如何备份和恢复 LEDE 路由器的配置文件?
如何备份和恢复...
2023年04月17日 -
如何在QQ上设置字体大小和样式?
在QQ上设置字...
2023年05月15日 -
怎么诊断网站是否被降权
网站降权是指搜...
2023年07月21日