14.5 二叉查找树
Input:
1 \
2 /
3 Output: [1,2,3]
vector<int> preorderTraversal(TreeNode* root) { vector<int> ret;
if (!root) { return ret;
} stack<TreeNode*> s;
s.push(root);
while (!s.empty()) { TreeNode* node = s.top();
s.pop();
ret.push_back(node->val);
if (node->right) { s.push(node->right); //
} if (node->left) {
s.push(node->left);
} }
return ret;
}
14.5
Binary Search Tree, BST
O¹n log nº

14.1:
template <class T> class BST {
struct Node { T data;
Node* left;
Node* right;
};
Node* root;
Node* makeEmpty(Node* t) { if (t == NULL) return NULL;
makeEmpty(t->left);
makeEmpty(t->right);
delete t;
return NULL;
}
Node* insert(Node* t, T x) { if (t == NULL) {
t = new Node;
t->data = x;
t->left = t->right = NULL;
} else if (x < t->data) { t->left = insert(t->left, x);
} else if (x > t->data) { t->right = insert(t->right, x);
} return t;
}
Node* find(Node* t, T x) { if (t == NULL) return NULL;
if (x < t->data) return find(t->left, x);
if (x > t->data) return find(t->right, x);
return t;
Node* findMin(Node* t) { if (t == NULL || t->left == NULL) return t;
return findMin(t->left);
}
Node* findMax(Node* t) { if (t == NULL || t->right == NULL) return t;
return findMax(t->right);
}
Node* remove(Node* t, T x) { Node* temp;
if (t == NULL) return NULL;
else if (x < t->data) t->left = remove(t->left, x);
else if (x > t->data) t->right = remove(t->right, x);
else if (t->left && t->right) { temp = findMin(t->right);
t->data = temp->data;
t->right = remove(t->right, t->data);
} else { temp = t;
if (t->left == NULL) t = t->right;
else if (t->right == NULL) t = t->left;
delete temp;
} return t;
}
public:
BST(): root(NULL) {}
~BST() { root = makeEmpty(root);
}
void insert(T x) { insert(root, x);
}
void remove(T x) { remove(root, x);
} };
99. Recover Binary Search Tree (Hard)
Input:
3 / \
14 /
2 Output:
2 / \
14 /
3
23
prev prev
// void recoverTree(TreeNode* root) {
TreeNode *mistake1 = nullptr, *mistake2 = nullptr, *prev = nullptr;
inorder(root, mistake1, mistake2, prev);
if (mistake1 && mistake2) { int temp = mistake1->val;
mistake1->val = mistake2->val;
mistake2->val = temp;
} }
// void inorder(TreeNode* root, TreeNode*& mistake1, TreeNode*& mistake2, TreeNode
*& prev) { if (!root) {
return;
} if (root->left) {
inorder(root->left, mistake1, mistake2, prev);
} if (prev && root->val < prev->val) {
if (!mistake1) { mistake1 = prev;
mistake2 = root;
} else { mistake2 = root;
} cout << mistake1->val;
cout << mistake2->val;
prev = root;
if (root->right) { inorder(root->right, mistake1, mistake2, prev);
全站分卷索引 · 68 卷
- 11 题目分类
- 22 最易懂的贪心算法
- 32.3 区间问题
- 42.4 练习
- 53 玩转双指针
- 63.2 Two Sum
- 73.4 快慢指针
- 83.5 滑动窗口
- 93.6 练习
- 104 居合斩!二分查找
- 114.3 查找区间
- 124.4 旋转数组查找数字
- 134.5 练习
- 145 千奇百怪的排序算法
- 155.2 快速选择
- 165.3 桶排序
- 175.4 练习
- 186 一切皆可搜索
- 196.3 回溯法
- 206.4 广度优先搜索
- 216.5 练习
- 227 深入浅出动态规划
- 237.3 基本动态规划:二维
- 247.4 分割类型题
- 257.5 子序列问题
- 267.6 背包问题
- 277.7 字符串编辑
- 287.8 股票交易
- 297.9 练习
- 308 化繁为简的分治法
- 318.3 练习
- 329 巧解数学问题
- 339.4 数字处理
- 349.5 随机与取样
- 359.6 练习
- 3610 神奇的位运算
- 3710.3 二进制特性
- 3810.4 练习
- 3911 妙用数据结构
- 4011.2 数组
- 4111.3 栈和队列
- 4211.4 单调栈
- 4311.5 优先队列
- 4411.6 双端队列
- 4511.7 哈希表
- 4611.8 多重集合和映射
- 4711.9 前缀和与积分图
- 4811.10 练习
- 11.10
- 566. Reshape the Matrix (Easy)
- 225. Implement Stack using Queues (Easy)
- 503. Next Greater Element II (Medium)
- 217. Contains Duplicate (Easy)
- 697. Degree of an Array (Easy)
- 594. Longest Harmonious Subsequence (Easy)
- 287. Find the Duplicate Number (Medium)
- 313. Super Ugly Number (Medium)
- 870. Advantage Shuffle (Medium)
- 307. Range Sum Query - Mutable (Medium)
- 4912 令人头大的字符串
- 5012.3 字符串理解
- 5112.4 字符串匹配
- 5212.5 练习
- 5313 指针三剑客之一:链表
- 5413.3 其它链表技巧
- 5513.4 练习
- 5614 指针三剑客之二:树
- 5714.3 层次遍历
- 5814.4 前中后序遍历
- 5914.5 二叉查找树
- 6014.6 字典树
- 6114.7 练习
- 14.7
- 226. Invert Binary Tree (Easy)
- 617. Merge Two Binary Trees (Easy)
- 572. Subtree of Another Tree (Easy)
- 404. Sum of Left Leaves (Easy)
- 513. Find Bottom Left Tree Value (Easy)
- 538. Convert BST to Greater Tree (Easy)
- 235. Lowest Common Ancestor of a Binary Search Tree (Easy)
- 530. Minimum Absolute Difference in BST (Easy)
- 889. Construct Binary Tree from Preorder and Postorder Traversal (Medium)
- 106. Construct Binary Tree from Inorder and Postorder Traversal (Medium)
- 94. Binary Tree Inorder Traversal (Medium)
- 6215 指针三剑客之三:图
- 6315.3 拓扑排序
- 6415.4 练习
- 6516 更加复杂的数据结构
- 6616.3 复合数据结构
- 6716.4 练习
- 6817 后记