【C++刷题】二叉树进阶刷题

1. 根据二叉树创建字符串

class Solution {
public:/** ()的省略有两种情况* 1.左右都为空，省略* 2.左子树不为空，右子树为空，省略*/string tree2str(TreeNode* root){string s;if(root == nullptr){return s;}s += to_string(root->val);if(root->left){s += "(";s += tree2str(root->left);s +=")";}else if(root->right) // 为了应对左为空，右不为空的情况{s += "()";}if(root->right){s += "(";s += tree2str(root->right);s += ")";}return s;}
};

2. 二叉树的层序遍历

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root){vector<vector<int>> vv;queue<TreeNode*> q;int levelSize = 0;if(root == nullptr){return vv;}q.push(root);vector<int> v;while(!q.empty()){v.resize(0);levelSize = q.size();while(levelSize--){if((q.front())->left){q.push((q.front())->left);}if((q.front())->right){q.push((q.front())->right);}v.push_back((q.front())->val);q.pop();}vv.push_back(v);}return vv;}
};

3. 二叉树的层序遍历 II

只需将正着层序遍历的结果reverse()一下即可。

4. 二叉树的最近公共祖先

class Solution {
public:bool FindPath(TreeNode* root, TreeNode* x, stack<TreeNode*>& st){if(root == nullptr){return false;}st.push(root);if(root == x){return true;}if(FindPath(root->left, x, st)){return true;}if(FindPath(root->right, x, st)){return true;}st.pop();return false;}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q){stack<TreeNode*> pPath, qPath;FindPath(root, p, pPath); // 找从根节点root到p的路径FindPath(root, q, qPath); // 找从根节点root到q的路径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 InOrderConvert(TreeNode* cur, TreeNode*& prev){if(cur == nullptr){return;}InOrderConvert(cur->left, prev);// 双向链接cur->left = prev;if(prev){prev->right = cur;}// prev向后移prev = cur;InOrderConvert(cur->right, prev);}TreeNode* Convert(TreeNode* pRootOfTree){TreeNode* prev = nullptr;// 中序遍历进行链接InOrderConvert(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& prei, int inbegin, int inend){// 子树区间确认是否继续递归创建子树if(inbegin > inend)return nullptr;// 前序创建树TreeNode* root = new TreeNode(preorder[prei++]);// 中序分割左右子树int ini = inbegin;while(ini <= inend){if(inorder[ini] == root->val)break;else++ini;}root->left = _buildTree(preorder, inorder, prei, inbegin, ini - 1);root->right = _buildTree(preorder, inorder, prei, ini + 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:TreeNode* _buildTree(vector<int>& inorder, vector<int>& postorder, int& posti, int inbegin, int inend){if(inbegin > inend)return nullptr;TreeNode* root = new TreeNode(postorder[posti--]);int ini = inbegin;while(ini <= inend){if(inorder[ini] == root->val)break;else++ini;}root->right = _buildTree(inorder, postorder, posti, ini + 1, inend);root->left = _buildTree(inorder, postorder, posti, inbegin, ini - 1);return root;}TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder){int i = postorder.size() - 1;return _buildTree(inorder, postorder, i, 0, inorder.size() - 1);}
};