【一天一大 lee】 把二叉搜索树转换为累加树 (难度:简单)-Day20200921
【一天一大 lee】 把二叉搜索树转换为累加树 (难度:简单)-Day20200921
前端小书童
发布于 2020-09-24 14:35:25
发布于 2020-09-24 14:35:25
给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。
示例：
输入: 原始二叉搜索树:
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
}
Morris 遍历
Morris 遍历的核心思想是利用树的大量空闲指针，实现空间开销的极限缩减。其反序中序遍历规则总结如下：
- 如果当前节点的右子节点为空，处理当前节点，并遍历当前节点的左子节点；
- 如果当前节点的右子节点不为空，找到当前节点右子树的最左节点（该节点为当前节点中序遍历的前驱节点）；
- 如果最左节点的左指针为空，将最左节点的左指针指向当前节点，遍历当前节点的右子节点；
- 如果最左节点的左指针不为空，将最左节点的左指针重新置为空（恢复树的原状），处理当前节点，并将当前节点置为其左节点；
- 重复步骤 1 和步骤 2，直到遍历结束。
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
}
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-09-21，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录