1. 二叉树创建字符串
相信大部分人看了题目描述之后，都会和我一样一脸的懵逼。直到我看到了一个描述才恍然大悟
分为3种情况：
- 左右都为空 --省略
- 右为空，左不为空 – 省略
- 左为空，右不为空–不省略
这里复习一下二叉树的前序遍历、中序遍历、和后序遍历
前序的结果是：ABDEGCF
中序的结果是：DBGEACF
后序的结果是：DGEBFCA
class Solution {
public:
string tree2str(TreeNode* root) {
if (root == nullptr)
{
return "";
}
string str = to_string(root->val);
if (root->left || root->right) // 特别注意这个条件
{
str += "(";
str += tree2str(root->left);
str += ")";
}
if (root->right)
{
str += "(";
str += tree2str(root->right);
str += ")";
}
return str;
}
};
2. 二叉树的层序遍历
思路大致是这样的：
一个队列，接着一个levelSize来记录每层有几个数据，如果这个数字是0，则表示这层的数据出完
出3将9和20带到队列，levelSize为2 。如此循环下去。
如果这个队列不为空，就一直循环下去，直到这个队列为空为止。
代码实现：
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
queue<TreeNode*> q;
int levelSize = 0;
if (root)
{
q.push(root);
levelSize = 1;
}
vector<vector<int>> vv;
while (!q.empty()) // 如果队列不为空，就继续
{
// 通过levelSize控制一层一层的出
vector<int> v;
while (levelSize--)
{
TreeNode* front = q.front();
q.pop();
v.push_back(front->val);
if (front->left)
{
q.push(front->left);
}
if (front->right)
{
q.push(front->right);
}
}
vv.push_back(v);
// 更新下一层的个数
levelSize = q.size();
}
return vv;
}
};
3. 二叉树的层序遍历Ⅱ
这个题目与上一题目，差不多，我们只需要将最后的答案逆置即可
4. 二叉树的最近公共祖先
思路一：公共祖先的特征，如果一个在左子树，一个在右子树。那么这个节点就是公共祖先。
class Solution {
public:
bool isInTree(TreeNode* root, TreeNode* x) {
if (root == nullptr) {
return false;
}
return x == root
|| isInTree(root->left, x)
|| isInTree(root->right, x);
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == nullptr) {
return nullptr;
}
if (p == root || q == root) {
return root;
}
// 判断p节点是在root的左边还是右边
bool pInLeft = isInTree(root->left, p);
bool pInRight = !pInLeft;
// 判断q节点是在root的左边还是右边
bool qInLeft = isInTree(root->left, q);
bool qInRight = !qInLeft;
if ((pInLeft && qInRight) || (pInRight && qInLeft)) {
return root;
}
// 如果都在左边，则转换为在左树寻找公共祖先
else if (pInLeft && qInLeft) {
return lowestCommonAncestor(root->left, p, q);
}
else {
return lowestCommonAncestor(root->right, p, q);
}
}
};
思路二：公共祖先的特征，如果一个在我的左子树，一个在我的右子树，我就是公共祖先
如果是搜索二叉树可以优化到O(N)
- 一个比根小，一个比根大，根就是公共祖先
- 都比根小，递归左树查找
- 都比根大，递归右树查找
但是这个题目我们并不是搜索二叉树，要求优化到O(N)
这里只能使用另外一种思路，将p和q的路径求出来，放到容器当中，转换为路径相交问题
class Solution {
public:
bool getPath(TreeNode* root, TreeNode* x, stack<TreeNode*>& path) {
if (root == nullptr) {
return false;
}
path.push(root);
if (root == x) {
return true;
}
if (getPath(root->left, x, path)) {
return true;
}
if (getPath(root->right, x, path)) {
return true;
}
path.pop();
return false;
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
stack<TreeNode*> pPath, qPath;
getPath(root, p, pPath);
getPath(root, q, qPath);
while (pPath.size() != qPath.size()) {
if (pPath.size() > qPath.size()) {
pPath.pop();
}
else {
qPath.pop();
}
}
while (pPath.top() != qPath.top()) {
pPath.pop();
qPath.pop();
}
return pPath.top();
}
};
上述代码的关键在于找到每个节点的路径
5. 二叉搜索树与双向链表
看到这个题目我们的第一个想法可能是把所有的节点拿出来，然后尾插到一个双向链表上，其实并没有这么简单，我们能够想到的出题人当然也能够想到。
这个题目有以下几个要求：
我们需要在原树上进行操作。
class Solution {
public:
void inorderTraversal(TreeNode* cur, TreeNode*& prev) {
if (cur == nullptr) {
return;
}
inorderTraversal(cur->left, prev);
cur->left = prev;
if (prev) {
prev->right = cur;
}
prev = cur;
inorderTraversal(cur->right, prev);
}
TreeNode* Convert(TreeNode* pRootOfTree) {
TreeNode* prev = nullptr;
inorderTraversal(pRootOfTree, prev);
TreeNode* head = pRootOfTree;
while (head && head->left) {
head = head->left;
}
return head;
}
};
以上的这幅图是精髓所在
6. 从前序与中序遍历序列构造二叉树
class Solution {
public:
TreeNode* _buildTree(vector<int>& preorder, vector<int>& inorder, int& previ, int inbegin, int inend) {
if (inbegin > inend) {
return nullptr;
}
TreeNode* root = new TreeNode(preorder[previ]);
// 分割出左右区间
int rooti = inbegin;
while (rooti <= inend) {
if (inorder[rooti] == preorder[previ]) {
break;
}
else {
rooti++;
}
}
++previ;
// [inbegin, rooti - 1], rooti, [rooti + 1, inend]
root->left = _buildTree(preorder, inorder, previ, inbegin, rooti - 1);
root->right = _buildTree(preorder, inorder, previ, rooti + 1, inend);
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int i = 0;
return _buildTree(preorder, inorder, i, 0, inorder.size() - 1);
}
};
7. 二叉树的前序遍历(非递归)
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
TreeNode* cur = root;
vector<int> v;
while (cur || !st.empty()) {
// 1. 开始访问一棵树
// 2. 左路节点
// 3. 左路节点的右子树
while (cur) {
v.push_back(cur->val);
st.push(cur);
cur = cur->left;
}
// 访问右子树
TreeNode* top = st.top();
st.pop();
// 子问题访问右子树
cur = top->right;// 这个地方非常重要
}
return v;
}
};
8. 二叉树的中序遍历(非递归)
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
TreeNode* cur = root;
vector<int> v;
while (cur || !st.empty()) {
while (cur) {
st.push(cur);
cur = cur->left;
}
// 栈里面取到左路节点，左路节点的左子树访问完了
TreeNode* top = st.top();
st.pop();
v.push_back(top->val);
cur = top->right;
}
return v;
}
};
8. 二叉树的后序遍历(非递归)
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
TreeNode* cur = root;
vector<int> v;
TreeNode* prve = nullptr;
while (cur || !st.empty()) {
while (cur) {
st.push(cur);
cur = cur->left;
}
// 栈里面取到左路节点，左路节点的左子树访问完了
TreeNode* top = st.top();
// 右为空或者右已经访问过了，可以访问根节点
if (top->right == nullptr || top->right == prve) {
v.push_back(top->val);
st.pop();
prve = top;
}
else {
cur = top->right;
}
}
return v;
}
};
这里对非递归的三种代码进行对比：文章来源：https://www.toymoban.com/news/detail-499083.html
文章来源地址https://www.toymoban.com/news/detail-499083.html
到了这里，关于【数据结构】二叉树经典题目的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
