C++伸展树介绍以及红黑树的实现
1. 伸展树介绍
一种与 AVL 树类似的改进的二叉搜索树,称为 伸展树。是由 John Edward Hopcroft 和 Robert Endre Tarjan 于 1985 年共同发明的。与 AVL 树以及在并查集时的父指针表示的树的路径压缩一样,同属于自调整数据结构。
伸展树与红黑树是 C++ 中重要的平衡二叉搜索树。伸展树利用局部性原理,通过旋转将访问节点移至根部,优化热点数据查询。红黑树通过颜色约束确保路径长度平衡,提供稳定的 O(log n) 性能,广泛应用于 STL 容器。文章涵盖伸展树展开操作、红黑树五大性质、插入删除修复策略、代码实现细节及验证方法,并附带常见 OJ 题目解析。

一种与 AVL 树类似的改进的二叉搜索树,称为 伸展树。是由 John Edward Hopcroft 和 Robert Endre Tarjan 于 1985 年共同发明的。与 AVL 树以及在并查集时的父指针表示的树的路径压缩一样,同属于自调整数据结构。
在讨论 AVL 树时,主要关注点在于保持树的高度平衡。然而,对于二叉搜索树来说,它主要用于内存中目录的编制,因此,快速插入、搜索、删除元素才是我们关心的问题,而不是树的形状。通过平衡树可以提高效率,但这不是唯一的方法。伸展树就是另一种提高搜索效率的方法。
它参照了以下两种想法:
每当访问(包括搜索、插入或删除)一个结点 s 时,伸展树就执行一次叫做'展开'的过程。'展开'将结点 s 移到二叉搜索树的根部。当删除结点 s 时,'展开'把结点 s 的父结点上移到根结点。就像 AVL 树,一次'展开'由一组旋转组成。旋转有三种类型:单旋转、一字形旋转和之字形旋转。
被访问结点 s'展开'过程的算法描述如下:
void splaying(Node* g, Node* p, Node* s) {
// g 是 p 的父结点,p 是 s 的父结点。算法将 s 移到根结点位置
while (s != root) {
if (s->parent == root) {
// 进行单旋转,将 s 调整为根结点
rotate(s->parent);
} else if (isSameDirection(s, p, g)) {
// 进行一字形双旋转,将 s 上移
rotate(p); rotate(g);
} else {
// s 与它的前驱 p,g 是异构形状,进行之字形双旋转,将 s 上移
rotate(s); rotate(g);
}
}
}
伸展树并不要求每一个操作都是高效的,但是对于一个有 n 个结点的树结构,并执行 m 次操作的情形,可能一次插入或搜索操作需要花费 O(n) 时间,当 m >= n 时,所有 m 个操作总共需要 O(m log n) 时间,从而使每次访问操作所花费的平均时间达到 O(log n),从整体上保持较高的时间性能。
图描述了伸展树是如何通过'展开'实现自调整的。首先在伸展树中搜索某个值,搜索过程与二叉搜索树完全一样,一旦搜索成功,就执行'展开'过程将该结点上移到根结点位置。
伸展树的插入操作与二叉搜索树相同,但结点一经插入之后立即展开到根结点。同样,从伸展树中删除一个结点的操作也与二叉搜索树相同,但需要把被删结点的父结点展开到根结点。伸展树与 AVL 树在操作上稍有不同。伸展树的调整与结点被访问(包括搜索、插入、删除)的频率有关,能够进行更合理的调整。而 AVL 树的结构调整只与插入、删除的顺序有关,与访问的频率无关。
红黑树是一棵二叉搜索树,它的每个结点增加一个存储位来表示结点的颜色,可以是红色或者黑色。通过对任何一条从根到叶子路径上各个结点的颜色进行约束,红黑树确保没有一条路径会比其他路径长出 2 倍,因而是接近平衡的。
红黑树是这样的一棵二叉搜索树:树中的每一个结点的颜色不是黑色就是红色。可以把一棵红黑树视为一棵扩充二叉树,用外部结点表示空指针。
从红黑树中任一结点 x 出发(不包括结点 x),到达一个外部结点的任一路径上的黑结点个数叫做结点 x 的黑高度,亦称为结点的阶记作 bh(x)。红黑树的黑高度定义为其根结点的黑高度。
另一种等价的定义是看结点指针的颜色。从父结点到黑色子女结点的指针为黑色的,从父结点到红色子女结点的指针为红色的。
结论 1:设从根到外部结点的路径长度 (Path Length, PL) 为该路径上指针的个数,如果 P 与 Q 是红黑树中的两条从根到外部结点的路径,则有:PL(P) <= 2 * PL(Q)。
结论 2:设 h 是一棵红黑树的高度(不包括外部结点),n 是树中内部结点的个数,r 是根结点的黑高度,则以下关系式成立: (1) h <= 2r (2) n >= 2^r - 1 (3) h <= 2 * log2(n + 1)
由于红黑树的高度最大为 2 * log2(n + 1),所以,搜索、插入、删除操作的时间复杂性为 O(log n)。注意,最差情况下的红黑树的高度大于最差情况下具有相同结点个数数的 AVL 树的高度,近似于 1.44 * log2(n + 2)。
红黑树继承了二叉搜索树的定义,一些数据成员和成员函数可以直接使用二叉搜索树的成员。
《算法导论》等书籍上补充了一条每个叶子结点 (NIL) 都是黑色的规则。它这里所指的叶子结点不是传统意义上的叶子结点,而是我们说的空结点,有些书籍上也把 NIL 叫做外部结点。NIL 是为了方便准确的标识出所有路径,《算法导论》在后续实现的细节中也忽略了 NIL 结点,所以我们知道一下这个概念即可。
假设 N 是红黑树树中结点数量,h 最短路径的长度,那么,由此推出,也就是意味着红黑树增删查改最坏也就是走最长路径,那么 2h - 1 <= N < 2^(2*h) - 1。由此推出 h ≈ logN,也就是意味着红黑树增删查改最坏也就是走最长路径,那么时间复杂度还是 O(log N)。
红黑树的表达相对 AVL 树要抽象一些,AVL 树通过高度差直观的控制了平衡。红黑树通过性质的颜色约束,间接的实现了近似平衡,他们效率都是同一档次,但是相对而言,插入相同数量的结点,红黑树的旋转次数是更少的,因为它对平衡的控制没那么严格。
// RBTree.h
#pragma once
#include <utility>
enum Colour { RED, BLACK };
template<class K, class V>
struct RBTreeNode {
std::pair<K, V> _kv;
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
Colour _col;
RBTreeNode(const std::pair<K, V>& kv) : _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED) {}
};
template<class K, class V>
class RBTree {
typedef RBTreeNode<K, V> Node;
public:
bool Insert(const std::pair<K, V>& kv) {
if (_root == nullptr) {
_root = new Node(kv);
_root->_col = BLACK;
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur) {
if (cur->_kv.first < kv.first) {
parent = cur;
cur = cur->_right;
} else if (cur->_kv.first > kv.first) {
parent = cur;
cur = cur->_left;
} else {
return false; // Key exists
}
}
cur = new Node(kv);
cur->_col = RED;
if (parent->_kv.first < kv.first) {
parent->_right = cur;
} else {
parent->_left = cur;
}
cur->_parent = parent;
while (parent && parent->_col == RED) {
Node* grandfather = parent->_parent;
if (grandfather->_left == parent) {
Node* uncle = grandfather->_right;
// 叔叔存在且为红 -> 变色
if (uncle && uncle->_col == RED) {
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
} else {
// 叔叔不存在,或者叔叔存在且为黑 -> 旋转 + 变色
if (cur == parent->_left) {
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
} else {
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
} else {
Node* uncle = grandfather->_left;
// 叔叔存在且为红 -> 变色
if (uncle && uncle->_col == RED) {
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
} else {
// 叔叔不存在,或者存在且为黑 -> 旋转 + 变色
if (cur == parent->_right) {
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
} else {
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return true;
}
void InOrder() {
_InOrder(_root);
std::cout << std::endl;
}
bool IsBalance() {
if (_root == nullptr) return true;
if (_root->_col == RED) return false;
Node* leftMost = _root;
int blackRef = 0;
while (leftMost) {
if (leftMost->_col == BLACK) ++blackRef;
leftMost = leftMost->_left;
}
return Check(_root, 0, blackRef);
}
int Height() {
return _Height(_root);
}
int Size() {
return _Size(_root);
}
Node* Find(const K& key) {
Node* cur = _root;
while (cur) {
if (cur->_kv.first < key) {
cur = cur->_right;
} else if (cur->_kv.first > key) {
cur = cur->_left;
} else {
return cur;
}
}
return nullptr;
}
private:
int _Size(Node* root) {
return root == nullptr ? 0 : _Size(root->_left) + _Size(root->_right) + 1;
}
int _Height(Node* root) {
if (root == nullptr) return 0;
int leftHeight = _Height(root->_left);
int rightHeight = _Height(root->_right);
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
bool Check(Node* cur, int blackNum, const int blackNumRef) {
if (cur == nullptr) {
if (blackNum != blackNumRef) {
std::cout << "黑色节点的数量不相等" << std::endl;
return false;
}
return true;
}
if (cur->_col == RED && cur->_parent && cur->_parent->_col == RED) {
std::cout << cur->_kv.first << "->" << "连续的红色节点" << std::endl;
return false;
}
if (cur->_col == BLACK) ++blackNum;
return Check(cur->_left, blackNum, blackNumRef) && Check(cur->_right, blackNum, blackNumRef);
}
void _InOrder(Node* root) {
if (root == nullptr) return;
_InOrder(root->_left);
std::cout << root->_kv.first << " ";
_InOrder(root->_right);
}
void RotateR(Node* parent) {
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR) subLR->_parent = parent;
Node* parentParent = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (parent == _root) {
_root = subL;
subL->_parent = nullptr;
} else {
if (parentParent->_left == parent) {
parentParent->_left = subL;
} else {
parentParent->_right = subL;
}
subL->_parent = parentParent;
}
}
void RotateL(Node* parent) {
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL) subRL->_parent = parent;
Node* parentParent = parent->_parent;
subR->_left = parent;
parent->_parent = subR;
if (parent == _root) {
_root = subR;
subR->_parent = nullptr;
} else {
if (parentParent->_left == parent) {
parentParent->_left = subR;
} else {
parentParent->_right = subR;
}
subR->_parent = parentParent;
}
}
private:
Node* _root = nullptr;
};
测试代码示例:
#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
#include <ctime>
using namespace std;
#include "RBTree.h"
void TestRBTree1() {
RBTree<int, int> t;
int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
for (auto e : a) {
t.Insert({ e, e });
}
t.InOrder();
cout << t.IsBalance() << endl;
}
int main() {
TestRBTree1();
return 0;
}
由于每一棵红黑树都是二叉搜索树,可以使用与搜索普通二叉搜索树时所使用的完全相同的算法进行搜索。在搜索过程中不需使用颜色信息。对普通二叉搜索树进行搜索的时间复杂性为 O(h),对于红黑树则为 O(log n)。
说明:下图中假设我们把新增结点标识为 c (cur),c 的父亲标识为 p (parent),p 的父亲标识为 g (grandfather),p 的兄弟标识为 u (uncle)。
情况 1:变色 c 为红,p 为红,g 为黑,u 存在且为红,则将 p 和 u 变黑,g 变红。在把 g 当做新的 c,继续往上更新。
情况 2:单旋 + 变色 c 为红,p 为红,g 为黑,u 不存在或者 u 存在且为黑。需要旋转 + 变色。 如果 p 是 g 的左,c 是 p 的左,那么以 g 为旋转点进行右单旋,再把 p 变黑,g 变红即可。 如果 p 是 g 的右,c 是 p 的右,那么以 g 为旋转点进行左单旋,再把 p 变黑,g 变红即可。
情况 3:双旋 + 变色 c 为红,p 为红,g 为黑,u 不存在或者 u 存在且为黑。 如果 p 是 g 的左,c 是 p 的右,那么先以 p 为旋转点进行左单旋,再以 g 为旋转点进行右单旋,再把 c 变黑,g 变红即可。 如果 p 是 g 的右,c 是 p 的左,那么先以 p 为旋转点进行右单旋,再以 g 为旋转点进行左单旋,再把 c 变黑,g 变红即可。
bool Insert(const std::pair<K, V>& kv) {
if (_root == nullptr) {
_root = new Node(kv);
_root->_col = BLACK;
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur) {
if (cur->_kv.first < kv.first) {
parent = cur;
cur = cur->_right;
} else if (cur->_kv.first > kv.first) {
parent = cur;
cur = cur->_left;
} else {
return false;
}
}
cur = new Node(kv);
cur->_col = RED;
if (parent->_kv.first < kv.first) {
parent->_right = cur;
} else {
parent->_left = cur;
}
cur->_parent = parent;
while (parent && parent->_col == RED) {
Node* grandfather = parent->_parent;
if (parent == grandfather->_left) {
Node* uncle = grandfather->_right;
if (uncle && uncle->_col == RED) {
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
} else {
if (cur == parent->_left) {
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
} else {
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
} else {
Node* uncle = grandfather->_left;
if (uncle && uncle->_col == RED) {
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
} else {
if (cur == parent->_right) {
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
} else {
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return true;
}
Node* Find(const K& key) {
Node* cur = _root;
while (cur) {
if (cur->_kv.first < key) {
cur = cur->_right;
} else if (cur->_kv.first > key) {
cur = cur->_left;
} else {
return cur;
}
}
return nullptr;
}
这里获取最长路径和最短路径,检查最长路径不超过最短路径的 2 倍是不可行的,因为就算满足这个条件,红黑树也可能颜色不满足性质。我们还是去检查性质,满足这些性质,一定能保证最长路径不超过最短路径的 2 倍。
bool Check(Node* root, int blackNum, const int refNum) {
if (root == nullptr) {
if (refNum != blackNum) {
std::cout << "存在黑色结点的数量不相等的路径" << std::endl;
return false;
}
return true;
}
if (root->_col == RED && root->_parent && root->_parent->_col == RED) {
std::cout << root->_kv.first << "存在连续的红⾊结点" << std::endl;
return false;
}
if (root->_col == BLACK) {
blackNum++;
}
return Check(root->_left, blackNum, refNum) && Check(root->_right, blackNum, refNum);
}
bool IsBalance() {
if (_root == nullptr) return true;
if (_root->_col == RED) return false;
int refNum = 0;
Node* cur = _root;
while (cur) {
if (cur->_col == BLACK) {
++refNum;
}
cur = cur->_left;
}
return Check(_root, 0, refNum);
}
红黑树的删除算法与二叉搜索树的删除算法类似,不同之处在于,在红黑树中执行一次二叉搜索树的删除运算,可能会破坏红黑树的特性,需要重新平衡。
在红黑树中真正删除的结点应是叶结点或只有一个子女的结点。若设被删除为 p,其唯一的子女为 s。结点 p 被删除后,结点 s 取代了它的位置。
如果被删结点 p 是红色的,删去它不存在问题。因为树中各结点的黑高度都没有改变,也不会出现连续两个红色结点,红黑树的特性仍然保持,不需执行重新平衡过程。
如果被删结点 p 是黑色的,一旦删去它,红黑树将不满足性质 3 的要求,因为在这条路径上黑色结点少了一个,从根到外部结点的黑高度将会降低。为此,可以将结点 u 看成具有额外的一重黑色,这样,任意包含结点 u 的路径上的黑高度仍保持删除前的值,就能恢复红黑树的特性。问题是在红黑树的定义中没有包括双重黑色的结点,因此必须通过旋转变换和改变结点的颜色,消除双重黑色结点,恢复红黑树的特性。
设 u 是被删结点 p 的唯一的子女结点。如果 u 是红色结点,可以把结点 u 染成黑色,从而恢复红黑树的特性。如果被删结点 p 是黑色结点,它的唯一的子女结点 u 也是黑色结点,就必须先将结点 p 摘下,将结点 u 链到其祖父结点 g 的下面。假设结点 u 成为结点 g 的右子女,v 是 u 的左兄弟。根据 v 的颜色,分以下两种情况讨论:
情况 1:结点 v 是黑色结点 若设结点 v 的左子女结点为 w。根据 w 的颜色又需分两种情况讨论:
情况 2:结点 v 是红色结点 考查 v 的右子女结点 r。根据红黑树的性质 2,r 一定是黑色结点。再看结点 r 的左子女结点 s。根据 s 的颜色,可以分为两种情况讨论。
当结点 u 是结点 g 的左子女的情况与上面讨论的情况是镜像的,只要左、右指针互换就可以了。
#include <iostream>
#include <algorithm>
using namespace std;
enum Color { RED, BLACK };
template<typename K, typename V>
struct RBNode {
K key;
V value;
Color color;
RBNode* parent;
RBNode* left;
RBNode* right;
RBNode(const K& k, const V& v, Color c = RED) : key(k), value(v), color(c), parent(nullptr), left(nullptr), right(nullptr) {}
};
template<typename K, typename V>
class RBTree {
private:
using Node = RBNode<K, V>;
Node* root;
Node* nil;
void left_rotate(Node* x) {
Node* y = x->right;
x->right = y->left;
if (y->left != nil) y->left->parent = x;
y->parent = x->parent;
if (x->parent == nil) root = y;
else if (x == x->parent->left) x->parent->left = y;
else x->parent->right = y;
y->left = x;
x->parent = y;
}
void right_rotate(Node* y) {
Node* x = y->left;
y->left = x->right;
if (x->right != nil) x->right->parent = y;
x->parent = y->parent;
if (y->parent == nil) root = x;
else if (y == y->parent->left) y->parent->left = x;
else y->parent->right = x;
x->right = y;
y->parent = x;
}
void insert_fixup(Node* z) {
while (z->parent->color == RED) {
if (z->parent == z->parent->parent->left) {
Node* uncle = z->parent->parent->right;
if (uncle->color == RED) {
z->parent->color = BLACK;
uncle->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent;
} else {
if (z == z->parent->right) {
z = z->parent;
left_rotate(z);
}
z->parent->color = BLACK;
z->parent->parent->color = RED;
right_rotate(z->parent->parent);
}
} else {
Node* uncle = z->parent->parent->left;
if (uncle->color == RED) {
z->parent->color = BLACK;
uncle->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent;
} else {
if (z == z->parent->left) {
z = z->parent;
right_rotate(z);
}
z->parent->color = BLACK;
z->parent->parent->color = RED;
left_rotate(z->parent->parent);
}
}
}
root->color = BLACK;
}
Node* bst_insert(const K& key, const V& value) {
Node* parent = nil;
Node* curr = root;
while (curr != nil) {
parent = curr;
if (key < curr->key) curr = curr->left;
else if (key > curr->key) curr = curr->right;
else {
curr->value = value;
return curr;
}
}
Node* new_node = new Node(key, value, RED);
new_node->parent = parent;
new_node->left = nil;
new_node->right = nil;
if (parent == nil) root = new_node;
else if (key < parent->key) parent->left = new_node;
else parent->right = new_node;
return new_node;
}
void inorder_traversal(Node* node) const {
if (node == nil) return;
inorder_traversal(node->left);
cout << "[" << node->key << ":" << node->value << "," << (node->color == RED ? "红" : "黑") << "] ";
inorder_traversal(node->right);
}
public:
RBTree() {
nil = new Node(K(), V(), BLACK);
root = nil;
}
~RBTree() {
delete nil;
}
void insert(const K& key, const V& value) {
Node* new_node = bst_insert(key, value);
if (new_node->color == RED) insert_fixup(new_node);
}
void inorder() const {
inorder_traversal(root);
cout << endl;
}
Node* find(const K& key) const {
Node* curr = root;
while (curr != nil) {
if (key < curr->key) curr = curr->left;
else if (key > curr->key) curr = curr->right;
else return curr;
}
return nullptr;
}
};
int main() {
RBTree<int, string> rb_tree;
rb_tree.insert(10, "A");
rb_tree.insert(20, "B");
rb_tree.insert(30, "C");
rb_tree.insert(15, "D");
rb_tree.insert(25, "E");
rb_tree.insert(5, "F");
cout << "红黑树中序遍历(键值:颜色):" << endl;
rb_tree.inorder();
auto node = rb_tree.find(15);
if (node) {
cout << "\n查找键 15:值=" << node->value << ",颜色=" << (node->color == RED ? "红" : "黑") << endl;
}
return 0;
}
class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
if (root == nullptr) return new TreeNode(val);
TreeNode* cur = root;
while (cur != nullptr) {
if (val < cur->val) {
if (cur->left == nullptr) {
cur->left = new TreeNode(val);
break;
} else {
cur = cur->left;
}
} else {
if (cur->right == nullptr) {
cur->right = new TreeNode(val);
break;
} else {
cur = cur->right;
}
}
}
return root;
}
};
class Solution {
private:
void inorder(TreeNode* root, vector<int>& nums) {
if (root == nullptr) return;
inorder(root->left, nums);
nums.push_back(root->val);
inorder(root->right, nums);
}
TreeNode* build(const vector<int>& nums, int start, int end) {
if (start > end) return nullptr;
int mid = start + (end - start) / 2;
TreeNode* node = new TreeNode(nums[mid]);
node->left = build(nums, start, mid - 1);
node->right = build(nums, mid + 1, end);
return node;
}
public:
TreeNode* balanceBST(TreeNode* root) {
vector<int> nums;
inorder(root, nums);
return build(nums, 0, nums.size() - 1);
}
};
class Solution {
private:
int getHeight(TreeNode* node) {
if (node == nullptr) return 0;
int leftHeight = getHeight(node->left);
if (leftHeight == -1) return -1;
int rightHeight = getHeight(node->right);
if (rightHeight == -1) return -1;
if (abs(leftHeight - rightHeight) > 1) return -1;
return max(leftHeight, rightHeight) + 1;
}
public:
bool isBalanced(TreeNode* root) {
return getHeight(root) != -1;
}
};
class BSTIterator {
private:
vector<int> inorderList;
int idx;
void inorder(TreeNode* node) {
if (node == nullptr) return;
inorder(node->left);
inorderList.push_back(node->val);
inorder(node->right);
}
public:
BSTIterator(TreeNode* root) {
inorder(root);
idx = 0;
}
int next() {
return inorderList[idx++];
}
bool hasNext() {
return idx < inorderList.size();
}
};
class Solution {
private:
int helper(TreeNode* node, int& maxSum) {
if (node == nullptr) return 0;
int leftContribution = max(helper(node->left, maxSum), 0);
int rightContribution = max(helper(node->right, maxSum), 0);
int currentPathSum = node->val + leftContribution + rightContribution;
maxSum = max(maxSum, currentPathSum);
return node->val + max(leftContribution, rightContribution);
}
public:
int maxPathSum(TreeNode* root) {
int maxSum = INT_MIN;
helper(root, maxSum);
return maxSum;
}
};

微信公众号「极客日志」,在微信中扫描左侧二维码关注。展示文案:极客日志 zeeklog
使用加密算法(如AES、TripleDES、Rabbit或RC4)加密和解密文本明文。 在线工具,加密/解密文本在线工具,online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具,Base64 字符串编码/解码在线工具,online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具,Base64 文件转换器在线工具,online
将 Markdown(GFM)转为 HTML 片段,浏览器内 marked 解析;与 HTML转Markdown 互为补充。 在线工具,Markdown转HTML在线工具,online
将 HTML 片段转为 GitHub Flavored Markdown,支持标题、列表、链接、代码块与表格等;浏览器内处理,可链接预填。 在线工具,HTML转Markdown在线工具,online
通过删除不必要的空白来缩小和压缩JSON。 在线工具,JSON 压缩在线工具,online