二叉树
二叉树刷题框架
二叉树的定义:
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL);
};
1 二叉树的遍历方式
【1】前序遍历
class Solution {
public:
void traversal(TreeNode* node, vector<int>& vec) {
if (node == NULL) return;
vec.push_back(node->val);
traversal(node->left, vec);
traversal(node->right, vec);
}
vector<int> preorderTraversal(TreeNode* root) {
vector<int> result;
traversal(root, result);
return result;
}
};
【2】后序遍历
class Solution {
public:
void traversal(TreeNode* node, vector<int>& vec) {
if (node == NULL) return;
traversal(node->left, vec);
traversal(node->right, vec);
vec.push_back(node->val);
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int> result;
traversal(root, result);
return result;
}
};
【3】中序遍历
class Solution {
public:
void traversal(TreeNode* node, vector<int>& vec) {
if (node == NULL) return;
traversal(node->left, vec);
vec.push_back(node->val);
traversal(node->right, vec);
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
traversal(root, result);
return result;
}
};
【4】层序遍历
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> result;
queue<TreeNode*> que;
if (root != NULL) que.push(root);
while (!que.empty()) {
vector<int> vec;
int size = que.size();
for (int i = 0; i < size; i++) {
TreeNode* node = que.front();
que.pop();
vec.push_back(node->val);
if (node->left) que.push(node->left);
if (node->right) que.push(node->right);
}
result.push_back(vec);
}
return result;
}
};
2 二叉树的属性
【1】101. 对称二叉树
class Solution {
public:
bool compare(TreeNode* left, TreeNode* right) {
if (left != NULL && right == NULL) return false;
else if (left == NULL && right != NULL) return false;
else if (left == NULL && right == NULL) return true;
else if (left->val != right->val) return false;
bool outside = compare(left->left, right->right);
bool inside = compare(left->right, right->left);
return outside && inside;
}
bool isSymmetric(TreeNode* root) {
if (root == NULL) return true;
return compare(root->left, root->right);
}
};
【2】104. 二叉树的最大深度
迭代法:
class Solution {
public:
int maxDepth(TreeNode* root) {
if (root == NULL) return 0;
int depth = 0;
queue<TreeNode*> que;
que.push(root);
while (!que.empty()) {
int size = que.size();
depth++;
while (size--) {
TreeNode* node = que.front();
que.pop();
if (node->left) que.push(node->left);
if (node->right) que.push(node->right);
}
}
return depth;
}
};
递归法:
class Solution {
public:
int getDepth(TreeNode* node) {
if (node == NULL) return 0;
int left = getDepth(node->left);
int right = getDepth(node->right);
return 1 + max(left, right);
}
int maxDepth(TreeNode* root) {
return getDepth(root);
}
};
【3】111.二叉树的最小深度
递归法:
class Solution {
public:
int getDepth(TreeNode* node) {
if (node == NULL) return 0;
int left = getDepth(node->left);
int right = getDepth(node->right);
if (node->left != NULL && node->right == NULL) return 1 + left;
if (node->left == NULL && node->right != NULL) return 1 + right;
return 1 + min(left, right);
}
int minDepth(TreeNode* root) {
return getDepth(root);
}
};
迭代法:
class Solution {
public:
int minDepth(TreeNode* root) {
queue<TreeNode*> que;
if (root == NULL) return 0;
que.push(root);
int depth = 0;
while (!que.empty()) {
int size = que.size();
depth++;
while (size--) {
TreeNode* node = que.front();
que.pop();
if (node->left) que.push(node->left);
if (node->right) que.push(node->right);
if (node->left == NULL && node->right == NULL) return depth;
}
}
return depth;
}
};
【4】222. 完全二叉树的节点个数
递归法:
class Solution {
public:
int getNum(TreeNode* node) {
if (node == NULL) return 0;
int left = getNum(node->left);
int right = getNum(node->right);
return 1 + left + right;
}
int countNodes(TreeNode* root) {
return getNum(root);
}
};
迭代法:
class Solution {
public:
int countNodes(TreeNode* root) {
queue<TreeNode*> que;
if (root == NULL) return 0;
que.push(root);
int num = 0;
while (!que.empty()) {
int size = que.size();
while (size--) {
TreeNode* node = que.front();
que.pop();
num++;
if (node->left) que.push(node->left);
if (node->right) que.push(node->right);
}
}
return num;
}
};
【5】110. 平衡二叉树
class Solution {
public:
int getHeight(TreeNode* node) {
if (node == NULL) return 0;
int left = getHeight(node->left);
if (left == -1) return -1;
int right = getHeight(node->right);
if (right == -1) return -1;
return abs(left - right) > 1 ? -1 : 1 + max(left, right);
}
bool isBalanced(TreeNode* root) {
return getHeight(root) == -1 ? false : true;
}
};
【6】257. 二叉树的所有路径
class Solution {
public:
void traversal(TreeNode* node, string path, vector<string>& result) {
path += to_string(node->val);
if (node->left == NULL && node->right == NULL) {
result.push_back(path);
return;
}
if (node->left) traversal(node->left, path + "->", result);
if (node->right) traversal(node->right, path + "->", result);
}
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> result;
string path;
if (root == NULL) return result;
traversal(root, path, result);
return result;
}
};
【7】404. 左叶子之和
class Solution {
public:
int sumOfLeftLeaves(TreeNode* root) {
if (root == NULL) return 0;
int left = sumOfLeftLeaves(root->left);
if (root->left && root->left->left == NULL && root->left->right == NULL) {
left = root->left->val;
}
int right = sumOfLeftLeaves(root->right);
return left + right;
}
};
【8】513. 找树左下角的值
迭代法:
class Solution {
public:
int findBottomLeftValue(TreeNode* root) {
queue<TreeNode*> que;
que.push(root);
int val = 0;
while (!que.empty()) {
int size = que.size();
for (int i = 0; i < size; i++) {
TreeNode* node = que.front();
que.pop();
if (i == 0) val = node->val;
if (node->left) que.push(node->left);
if (node->right) que.push(node->right);
}
}
return val;
}
};
【9】112. 路径总和
class Solution {
public:
bool pathSum(TreeNode* node, int count) {
if (node->left == NULL && node->right == NULL && count == 0) return true;
if (node->left == NULL && node->right == NULL) return false;
if (node->left) {
count -= node->left->val;
if (pathSum(node->left, count)) return true;
count += node->left->val;
}
if (node->right) {
count -= node->right->val;
if (pathSum(node->right, count)) return true;
count += node->right->val;
}
return false;
}
bool hasPathSum(TreeNode* root, int targetSum) {
if (root == NULL) return false;
return pathSum(root, targetSum - root->val);
}
};
【10】543. 二叉树的直径
class Solution {
public:
int ans;
int Depth(TreeNode* node) {
if (node == NULL) return 0;
int left = Depth(node->left);
int right = Depth(node->right);
ans = max(ans, 1 + left + right);
return 1 + max(left, right);
}
int diameterOfBinaryTree(TreeNode* root) {
ans = 1;
Depth(root);
return ans - 1;
}
};
【11】124. 二叉树中的最大路径和
class Solution {
public:
int ans = INT_MIN;
int dfs(TreeNode* node) {
if (node == NULL) return 0;
ans = max(ans, node->val);
int lSum = dfs(node->left);
int rSum = dfs(node->right);
lSum = max(0, lSum); rSum = max(0, rSum);
ans = max(ans, node->val + lSum + rSum);
return max(node->val + lSum, node->val + rSum);
}
int maxPathSum(TreeNode* root) {
ans = max(ans, dfs(root));
return ans;
}
};
3 二叉树的修改和构造
【1】226. 翻转二叉树
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root == NULL) return root;
swap(root->left, root->right);
if (root->left) invertTree(root->left);
if (root->right) invertTree(root->right);
return root;
}
};
【2】106. 从中序与后序遍历序列构造二叉树
class Solution {
public:
TreeNode* traversal(vector<int>& inorder, vector<int>& postorder) {
if (postorder.size() == 0) return NULL;
int rootValue = postorder[postorder.size() - 1];
TreeNode* root = new TreeNode(rootValue);
if (postorder.size() == 1) return root;
int qiege;
for (qiege = 0; qiege <= inorder.size(); qiege++) {
if (inorder[qiege] == root->val) break;
}
vector<int> leftInorder(inorder.begin(), inorder.begin() + qiege);
vector<int> rightInorder(inorder.begin() + qiege + 1, inorder.end());
postorder.resize(postorder.size() - 1);
vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());
vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end());
root->left = traversal(leftInorder, leftPostorder);
root->right = traversal(rightInorder, rightPostorder);
return root;
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if (inorder.size() == 0 || postorder.size() == 0) return NULL;
return traversal(inorder, postorder);
}
};
【3】654. 最大二叉树
构造树一般采用的是前序遍历
class Solution {
public:
TreeNode* traversal(vector<int>& nums, int left, int right) {
if (left >= right) return NULL;
int index = left;
for (int i = left + 1; i < right; i++) {
if (nums[i] > nums[index]) index = i;
}
TreeNode* root = new TreeNode(nums[index]);
root->left = traversal(nums, left, index);
root->right = traversal(nums, index + 1, right);
return root;
}
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
return traversal(nums, 0, nums.size());
}
};
【4】617. 合并二叉树
class Solution {
public:
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
if (root1 == NULL) return root2;
if (root2 == NULL) return root1;
root1->val += root2->val;
root1->left = mergeTrees(root1->left, root2->left);
root1->right = mergeTrees(root1->right, root2->right);
return root1;
}
};
【5】114. 二叉树展开为链表
class Solution {
public:
void traversal(TreeNode* node) {
if (node == NULL) return;
traversal(node->left);
traversal(node->right);
TreeNode* left = node->left;
TreeNode* right = node->right;
node->left = NULL;
node->right = left;
while (node->right) node = node->right;
node->right = right;
return;
}
void flatten(TreeNode* root) {
traversal(root);
return;
}
};
4 求二叉树的属性
【1】700. 二叉搜索树中的搜索
class Solution {
public:
TreeNode* searchBST(TreeNode* root, int val) {
while (root != NULL) {
if (root->val > val) {
root = root->left;
} else if (root->val < val) {
root = root->right;
} else return root;
}
return root;
}
};
【2】98. 验证二叉搜索树
class Solution {
public:
long long maxVel = LONG_MIN;
bool isValidBST(TreeNode* root) {
if (root == NULL) return true;
bool left = isValidBST(root->left);
if (root->val > maxVel) maxVel = root->val;
else return false;
bool right = isValidBST(root->right);
return left && right;
}
};
【3】530. 二叉搜索树的最小绝对差
遇到在二叉搜索树上求什么最值啊,差值之类的,就把它想成在一个有序数组上求最值,求差值
把二叉搜索树转换成有序数组,然后遍历一遍数组,就统计出来最小差值
class Solution {
public:
vector<int> vec;
int ans = INT_MAX;
void traversal(TreeNode* node) {
if (node == NULL) return;
traversal(node->left);
vec.push_back(node->val);
traversal(node->right);
}
int getMinimumDifference(TreeNode* root) {
traversal(root);
for (int i = 1; i < vec.size(); i++) {
ans = min(ans, vec[i] - vec[i - 1]);
}
return ans;
}
};
在递归中记录前一个节点的指针
class Solution {
public:
int result = INT_MAX;
TreeNode* pre = NULL;
void traversal(TreeNode* node) {
if (node == NULL) return;
traversal(node->left);
if (pre != NULL) result = min(result, node->val - pre->val);
pre = node;
traversal(node->right);
}
int getMinimumDifference(TreeNode* root) {
traversal(root);
return result;
}
};
【4】501. 二叉搜索树中的众数
class Solution {
public:
void traversal(TreeNode* cur, unordered_map<int, int>& map) {
if (cur == NULL) return;
map[cur->val]++;
traversal(cur->left, map);
traversal(cur->right, map);
return;
}
static bool cmp(const pair<int, int>& a, const pair<int, int>& b) {
return a.second > b.second;
}
vector<int> findMode(TreeNode* root) {
unordered_map<int, int> map;
vector<int> result;
if (root == NULL) return result;
traversal(root, map);
vector<pair<int, int>> vec(map.begin(), map.end());
sort(vec.begin(), vec.end(), cmp);
result.push_back(vec[0].first);
for (int i = 1; i < vec.size(); i++) {
if (vec[0].second == vec[i].second) result.push_back(vec[i].first);
else break;
}
return result;
}
};
【5】把二叉搜索树转换为累加树
class Solution {
public:
int pre = 0;
void traversal(TreeNode* node) {
if (node == NULL) return;
traversal(node->right);
node->val += pre;
pre = node->val;
traversal(node->left);
}
TreeNode* convertBST(TreeNode* root) {
if (root == NULL) return root;
traversal(root);
return root;
}
};
【6】230. 二叉搜索树中第K小的元素
class Solution {
public:
int maxVel = INT_MIN;
vector<int> vec;
void traversal(TreeNode* node) {
if (node == NULL) return;
traversal(node->left);
if (node->val > maxVel) {
vec.push_back(node->val);
maxVel = node->val;
}
traversal(node->right);
return;
}
int kthSmallest(TreeNode* root, int k) {
traversal(root);
return vec[k - 1];
}
};
【7】二叉树的右视图
class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
vector<int> result;
queue<TreeNode*> que;
if (root == NULL) return result;
que.push(root);
while (!que.empty()) {
int size = que.size();
for (int i = 0; i < size; i++) {
TreeNode* node = que.front();
que.pop();
if (i == (size - 1)) result.push_back(node->val);
if (node->left) que.push(node->left);
if (node->right) que.push(node->right);
}
}
return result;
}
};
5 二叉树的公共祖先问题
【1】236. 二叉树的最近公共祖先
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == p || root == q || root == NULL) return root;
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
if (left != NULL && right != NULL) return root;
if (left != NULL && right == NULL) return left;
else if (left == NULL && right != NULL) return right;
else return NULL;
}
};
【2】235. 二叉搜索树的最近公共祖先
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
while (root) {
if (root->val > q->val && root->val > p->val) root = root->left;
else if (root->val < q->val && root->val < p->val) root = root->right;
else return root;
}
return NULL;
}
};
6 二叉搜索树的修改和构造
【1】二叉搜索树的插入操作
class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
if (root == NULL) {
TreeNode* node = new TreeNode(val);
return node;
}
if (root->val > val) root->left = insertIntoBST(root->left, val);
if (root->val < val) root->right = insertIntoBST(root->right, val);
return root;
}
};
【2】450. 删除二叉搜索树中的节点
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if (root == NULL) return root;
if (root->val == key) {
if (root->left == NULL && root->right == NULL) {
delete root;
return NULL;
} else if (root->left == NULL) {
auto tmp = root->right;
delete root;
return tmp;
} else if (root->right == NULL) {
auto tmp = root->left;
delete root;
return tmp;
} else {
TreeNode* cur = root->right;
while (cur->left != NULL) {
cur = cur->left;
}
cur->left = root->left;
TreeNode* tmp = root;
root = root->right;
delete tmp;
return root;
}
}
if (root->val > key) root->left = deleteNode(root->left, key);
if (root->val < key) root->right = deleteNode(root->right, key);
return root;
}
};
【3】669. 修剪二叉搜索树
class Solution {
public:
TreeNode* trimBST(TreeNode* root, int low, int high) {
if (root == NULL) return root;
if (root->val < low) return trimBST(root->right, low, high);
if (root->val > high) return trimBST(root->left, low, high);
root->left = trimBST(root->left, low, high);
root->right = trimBST(root->right, low, high);
return root;
}
};
【4】108. 将有序数组转换为二叉搜索树文章来源:https://www.toymoban.com/news/detail-845970.html
class Solution {
public:
TreeNode* traversal(vector<int>& nums, int left, int right) {
if (left > right) return NULL;
int mid = left + (right - left) / 2;
TreeNode* root = new TreeNode(nums[mid]);
root->left = traversal(nums, left, mid - 1);
root->right = traversal(nums, mid + 1, right);
return root;
}
TreeNode* sortedArrayToBST(vector<int>& nums) {
return traversal(nums, 0, nums.size() - 1);
}
};
二叉树刷题专题到此结束,读者对题目有更好的解答欢迎讨论。文章来源地址https://www.toymoban.com/news/detail-845970.html
到了这里,关于【数据结构刷题专题】—— 二叉树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!