LeetCode-538. 把二叉搜索树转换为累加树
2020-09-21
问题地址
LeetCode538. 把二叉搜索树转换为累加树
问题描述
规则
- 给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。
注意
- 本题[力和 1038](https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/ “力和 1038″） 相同。
示例
- 示例一：
输入: 原始二叉搜索树:
5
/ \
2 13
输出: 转换为累加树:
18
/ \
20 13
解析
解题思路
- 二叉搜索树的特点：
- 任意节点左子树上的节点都比这个节点的值小；
- 任意节点右子树上的节点都比这个节点的值大；
- 二叉搜索树中不存在值相同的节点；
- 我们都知道中序遍历二叉搜索树将得到一个递增序列，例如题目所给示例中序遍历后为[2,5,13]。
- 反向遍历递增序列[2,5,13]并累加数组元素就得到[20,18,13]，这个操作就相当于是我们使用反向中序遍历搜索这个二叉搜索树。
数据操作分析
- 对于每一个节点先遍历他们的右子树，里面的节点都比当前节点大，累加到sum中；
- 使用sum加当前节点的值，再赋值给当前节点；（不论哪个节点sum保存着比当前节点大的值的和）；
- 递归左子树；
复杂度分析
- 时间复杂度
- 空间复杂度
编码实现
public class LeetCode0538_ConvertBST {
int sum = 0;
public TreeNode convertBST(TreeNode root) {
if (root != null) {
convertBST(root.right);
sum += root.val;
root.val = sum;
convertBST(root.left);
}
return root;
}
}
官方解法
前言
- 二叉搜索树是一棵空树，或者是具有下列性质的二叉树：
- 若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
- 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
- 它的左、右子树也分别为二叉搜索树。
- 由这样的性质我们可以发现，二叉搜索树的中序遍历是一个单调递增的有序序列。如果我们反序地中序遍历该二叉搜索树，即可得到一个单调递减的有序序列。
方法一：反序中序遍历
思路：
- 本题中要求我们将每个节点的值修改为原来的节点值加上所有大于它的节点值之和。这样我们只需要反序中序遍历该二叉搜索树，记录过程中的节点值之和，并不断更新当前遍历到的节点的节点值，即可得到题目要求的累加树。
复杂度分析：
- 时间复杂度:O(n)，其中 n 是二叉搜索树的节点数。每一个节点恰好被遍历一次。
- 空间复杂度：O(n),为递归过程中栈的开销，平均情况下为 O(\log n)，最坏情况下树呈现链状，为 O(n)
编码实现
class Solution {
int sum = 0;
public TreeNode convertBST(TreeNode root) {
if (root != null) {
convertBST(root.right);
sum += root.val;
root.val = sum;
convertBST(root.left);
}
return root;
}
}
方法二：Morris 遍历
思路
- 有一种巧妙的方法可以在线性时间内，只占用常数空间来实现中序遍历。这种方法由 J. H. Morris 在 1979 年的论文「Traversing Binary Trees Simply and Cheaply」中首次提出，因此被称为 Morris 遍历。
- Morris 遍历的核心思想是利用树的大量空闲指针，实现空间开销的极限缩减。其反序中序遍历规则总结如下：
- 如果当前节点的右子节点为空，处理当前节点，并遍历当前节点的左子节点；
- 如果当前节点的右子节点不为空，找到当前节点右子树的最左节点（该节点为当前节点中序遍历的前驱节点）；
- 如果最左节点的左指针为空，将最左节点的左指针指向当前节点，遍历当前节点的右子节点；
- 如果最左节点的左指针不为空，将最左节点的左指针重新置为空（恢复树的原状），处理当前节点，并将当前节点置为其左节点；
- 重复步骤 1 和步骤 2，直到遍历结束。
- 这样我们利用 Morris 遍历的方法，反序中序遍历该二叉搜索树，即可实现线性时间与常数空间的遍历。
复杂度分析：
- 时间复杂度:O(n)，其中 n 是二叉搜索树的节点数。没有左子树的节点只被访问一次，有左子树的节点被访问两次。
- 空间复杂度：O(1)。只操作已经存在的指针（树的空闲指针），因此只需要常数的额外空间。
编码实现
class Solution {
public TreeNode convertBST(TreeNode root) {
int sum = 0;
TreeNode node = root;
while (node != null) {
if (node.right == null) {
sum += node.val;
node.val = sum;
node = node.left;
} else {
TreeNode succ = getSuccessor(node);
if (succ.left == null) {
succ.left = node;
node = node.right;
} else {
succ.left = null;
sum += node.val;
node.val = sum;
node = node.left;
}
}
}
return root;
}
public TreeNode getSuccessor(TreeNode node) {
TreeNode succ = node.right;
while (succ.left != null && succ.left != node) {
succ = succ.left;
}
return succ;
}
}
精彩评论
跳转地址1：「手画图解」中序遍历，反向的
思路：
- 访问每一个节点时，我们希望有一个变量 sum，存着「比当前节点值大的所有节点值的和」。我们想到，BST 的中序遍历，节点值的打印顺序是递增的。如果先访问右子树，反向的中序遍历，节点值的打印顺序是递减的，之前访问的节点值都比当前的大，累加给 sum 。
-
对于每一个节点，先递归它的右子树，里面的节点值都比当前节点大，把它们累加给 sum。
- 再 “处理” 当前节点，sum 累加上当前节点值，更新当前节点值，
- 再递归它的左子树，sum 保存了比当前节点大的所有节点值的和，累加上当前节点值，并更新当前节点值。
- 这样，不管访问哪个节点，sum 始终保存了「比当前节点值大的所有节点值的和」。
编码实现
const convertBST = (root) => {
let sum = 0;
const inOrder = (root) => {
if (root == null) { // 遍历到null节点，开始返回
return;
}
if (root.right) { // 先进入右子树
inOrder(root.right);
}
sum += root.val; // 节点值累加给sum
root.val = sum; // 累加的结果，赋给root.val
if (root.left) { // 然后才进入左子树
inOrder(root.left);
}
};
inOrder(root); // 递归的入口，从根节点开始
return root;
}
复盘总结
- 前、中、后序遍历，都要对每一个节点「做一些事情」，只是「做一些事情」的时机不同，而已。
跳转地址2：538:为啥要反中序遍历？【递归】【迭代】详解
思路
- 一看到累加树，相信很多小伙伴一脸懵逼，如何累加，遇到一个节点，然后在遍历其他节点累加？怎么一想这么麻烦呢。然后发现这是一颗二叉搜索树，二叉搜索树啊，这是有序的啊。
- 那么有序的元素如果求累加呢？
- 其实这就是一棵树，大家可能看起来有点别扭，换一个角度来看，这就是一个有序数组[2, 5, 13]，求从后到前的累加数组，也就是[20, 18, 13]，大家是不是感觉这就是送分题了。
- 为什么变成数组就是送分题了呢，因为数组大家都知道怎么遍历啊，从后向前，挨个累加就完事了，这换成了二叉搜索树，看起来就别扭了一些是不是。
- 那么知道如何遍历这个二叉树，也就迎刃而解了，从树中可以看出累加的顺讯是 右中左，所以我们需要中序遍历反过来遍历这个二叉树，然后顺序累加就可以了。
- 遍历顺序如图所示：
- 以下我给出一种递归的写法，两种迭代法的写法，别问我为什么写出了这么多写法，把我写的这个题解彻底吃透二叉树的前中后序递归法和迭代法！！看了，你也能分分钟写出来三种写法！
编码实现一：递归
class Solution {
private:
int pre; // 记录前一个节点的数值
void traversal(TreeNode* cur) { // 右中左遍历
if (cur == NULL) return;
traversal(cur->right);
cur->val += pre;
pre = cur->val;
traversal(cur->left);
}
public:
TreeNode* convertBST(TreeNode* root) {
pre = 0;
traversal(root);
return root;
}
};
编码实现二：迭代
class Solution {
private:
int pre; // 记录前一个节点的数值
void traversal(TreeNode* root) {
stack<TreeNode*> st;
TreeNode* cur = root;
while (cur != NULL || !st.empty()) {
if (cur != NULL) {
st.push(cur);
cur = cur->right; // 右
} else {
cur = st.top(); // 中
st.pop();
cur->val += pre;
pre = cur->val;
cur = cur->left; // 左
}
}
}
public:
TreeNode* convertBST(TreeNode* root) {
pre = 0;
traversal(root);
return root;
}
};
编码实现三：迭代
class Solution {
private:
int pre; // 记录前一个节点的数值
void traversal(TreeNode* root) {
stack<TreeNode*> st;
if (root != NULL) st.push(root);
while (!st.empty()) {
TreeNode* node = st.top();
if (node != NULL) {
st.pop();
if (node->left) st.push(node->left); // 左
st.push(node); // 中
st.push(NULL);
if (node->right) st.push(node->right); // 右
} else {
st.pop();
node = st.top();
st.pop();
node->val += pre; // 处理中间节点
pre = node->val;
}
}
}
public:
TreeNode* convertBST(TreeNode* root) {
pre = 0;
traversal(root);
return root;
}
};