2022/12/31大约 6 分钟约 1823 字
二叉树
剑指 Offer 27. 二叉树的镜像 - leetcode
class Solution {
public:
TreeNode* mirrorTree(TreeNode* root) {
if(root == nullptr) return nullptr;
// 交换左右子树
swap(root->left, root->right);
// 递归
mirrorTree(root->left);
mirrorTree(root->right);
return root;
}
};二叉树的高度
一棵二叉树的高度是左、右子树的最大高度加 1，递归即得：
class Solution {
public:
int maxDepth(TreeNode* root) {
if(root == nullptr) return 0;
// 可以省略这 LH 和 RH 两个变量
int LH = maxDepth(root->left);
int RH = maxDepth(root->right);
return max(LH, RH) + 1;
}
};二叉树的遍历
前序遍历
递归解法比较简单，需要用一个辅助函数，用于保存访问结点的顺序：
class Solution {
public:
vector<int> preorderTraversal(TreeNode *root) {
vector<int> v;
preorder(root, v);
return v;
}
void preorder(TreeNode *root, vector<int> &v) {
if (root == nullptr) return;
v.push_back(root->val);
preorder(root->left, v);
preorder(root->right, v);
}
};非递归/迭代解法：
用一个栈模拟递归，先将根节点入栈，如果栈顶有孩子，则先出栈后依次将右孩子、左孩子压栈，直至栈为空停止。
为什么先压入右孩子？因为栈的特点是后进先出，先序遍历要求“根左右”，因此左孩子后入栈才能先被访问。
vector<int> preorderTraversal(TreeNode *root) {
vector<int> v;
if (!root) return v;
stack<TreeNode *> stack;
stack.push(root);
while (!stack.empty()) {
root = stack.top();
v.push_back(root->val);
stack.pop();
// 先右后左，后进先访问
if (root->right) stack.push(root->right);
if (root->left) stack.push(root->left);
}
return v;
}中序遍历
递归解法与前序遍历类似，只需要改动一下访问和递归的顺序：
class Solution {
public:
vector<int> inorderTraversal(TreeNode *root) {
vector<int> v;
inorder(root, v);
return v;
}
void inorder(TreeNode *root, vector<int> &v) {
if (root == nullptr) return;
inorder(root->left, v);
v.push_back(root->val);
inorder(root->right, v);
}
};非递归解法：
二叉树可以被左边界分解，因此使用一个栈，从根节点开始，只要有左子树就入栈，到叶子结点结束。从叶子结点开始出栈，出栈时带入右子树，重复以上步骤，直至栈空。
一句话就是：有左孩子就压栈，没有就弹出，弹出的结点判断有无左子树，周而复始。
vector<int> inorderTraversal(TreeNode *root) {
vector<int> v;
stack<TreeNode *> stack;
if (root) stack.push(root);
while (!stack.empty()) {
if (root->left) {
stack.push(root->left);
root = root->left;
continue;
}
TreeNode *top = stack.top();
stack.pop();
v.push_back(top->val);
if (top->right) {
stack.push(top->right);
root = top->right;
}
}
return v;
}这个过程有一种更巧妙的写法：
vector<int> inorderTraversal(TreeNode *root) {
vector<int> v;
stack<TreeNode *> stack;
while (root != nullptr || !stack.empty()) {
while (root != nullptr) { // 遍历到最左边的结点
stack.push(root);
root = root->left;
}
// 访问，并带入右子树
root = stack.top();
stack.pop();
v.push_back(root->val);
root = root->right;
}
return v;
}后序遍历
递归解法同样很简单，和前两种遍历方式类似：
class Solution {
public:
vector<int> postorderTraversal(TreeNode *root) {
vector<int> v;
postorder(root, v);
return v;
}
void postorder(TreeNode *root, vector<int> &v) {
if (root == nullptr) return;
postorder(root->left, v);
postorder(root->right, v);
v.push_back(root->val);
}
};非递归解法：
一种思路是借鉴前序遍历：如果用栈以“根右左”的先序遍历方式“收集”一遍结点，再依次访问栈中的结果，则恰好是“左右根”的后序遍历顺序。只需要基于前序遍历的方式修改即可：
vector<int> postorderTraversalNonR(TreeNode *root) {
vector<int> v;
if (!root) return v;
stack<TreeNode *> stack, stackCollect; // 收集栈
stack.push(root);
while (!stack.empty()) {
root = stack.top();
stackCollect.push(root); // 放进收集栈
stack.pop();
// 后进先出，调整为先访问右孩子
if (root->left) stack.push(root->left);
if (root->right) stack.push(root->right);
}
// 访问收集栈
while (!stackCollect.empty()) {
root = stackCollect.top();
v.push_back(root->val);
stackCollect.pop();
}
return v;
}这种方法并不是真正的后序遍历，但体现了前序和后序两种遍历的转换关系。类似的还有：迭代解法，时间复杂度 O(n)，空间复杂度 O(n)。
另一种思路是借鉴中序遍历，但遍历完最左侧的结点时，先访问对应右侧的结点再访问父结点。这种是真正的后序遍历，难点在于如何控制顺序。
主要思想：由于在某颗子树访问完成以后，接着就要回到其父结点去，因此可以用 prev 来记录上次访问的结点，回溯到父结点时，可以由此来判断上一个访问的结点是否为其右子树。
vector<int> postorderTraversal(TreeNode *root) {
vector<int> v;
stack<TreeNode *> stack;
TreeNode *prev = nullptr; // 记录上一个访问的结点，区分“根”和“右”
while (root != nullptr || !stack.empty()) {
while (root != nullptr) { // 遍历到最左边的结点
stack.push(root);
root = root->left;
}
// 从栈中弹出的元素，左子树已经访问完了
root = stack.top();
stack.pop();
// 现在判断是否存在右子树，或者上次有没有访问过
// 如果右子树没有被访问，那么将当前结点压栈，访问右子树
if (root->right && root->right != prev) {
// 记录当前路径分叉节点
stack.push(root);
root = root->right;
} else {
// 否则，没有右子树，或者上一个访问的节点是右子结点，
// 说明 root 的左右子树应均已访问
v.push_back(root->val);
prev = root; // 更新访问记录，回溯时由此判断右子树是否访问完成
root = nullptr; // 避免重复访问左子树
}
}
return v;
}层序遍历
迭代解法：借助队列先进先出的特点，当上一层结点出队列的时候，下一层的入队列，那么出队顺序恰好就是层序遍历的顺序。
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode *root) {
vector<vector<int>> list;
if (root == nullptr) return list;
queue<TreeNode*> q;
q.push(root);
while(!q.empty()) {
vector<int> v;
/*
第一层个数是1，一层出完下一层全部进入
一层走完，队列的 size 就是下一层的节点个数
*/
int size = (int) q.size();
for (int i = 0; i < size; i++) {
root = q.front();
q.pop();
v.push_back(root->val);
if(root->left) q.push(root->left);
if(root->right) q.push(root->right);
}
list.push_back(v);
}
return list;
}
};递归解法：
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode *root) {
vector<vector<int>> list;
if (root == nullptr) return list;
dfs(root, 0, list);
return list;
}
void dfs(TreeNode *root, int level, vector<vector<int>> &list) {
vector<int> v;
if (list.size() == level) list.push_back(v);
list.at(level).push_back(root->val);
if (root->left) dfs(root->left, level + 1, list);
if (root->right) dfs(root->right, level + 1, list);
}
};二叉树的宽度
求宽度相当于层序遍历，然后求结点最多那层的结点数。
求两结点的最近公共祖先
验证特殊二叉树
平衡二叉树
class Solution {
public:
bool isBalanced(TreeNode * root) {
return height(root) != -1;
}
// 高度是非负整数，返回 -1 表示不平衡
int height(TreeNode * root) {
if (root == nullptr) return 0;
int LH, RH; // 左右子树高度
// 如果左子树不是平衡树，实际上不用求右子树的高度
if ((LH = height(root - > left)) == -1 ||
(RH = height(root - > right)) == -1 ||
abs(LH - RH) > 1)
return -1;
return max(LH, RH) + 1;
}
};二叉搜索树
二叉搜索树（Binary Search Tree）也叫排序二叉树（Binary Sort Tree）