一、根据二叉树创建字符串
- to_string函数，数值转换字符串
- 加括号判断
- 加左括号：左空右不空 和 左不空
- 加右括号：右不空
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; } };
二、二叉树的层序遍历
思路：
- 利用queue层序，先让root入队
- 用levelSize作为循环次数，一层层处理
- 每个节点出队时，带左右孩子入队
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()) { 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; } };
三、二叉树的最近公共祖先
思路：
- 转换为路径相交问题，利用stack记录路径
- 写子函数GetPath，返回值为bool，每次先让root入栈，以前序遍历递归进行查找节点，如果找到返回true，最后没找到让当前root出栈，返回false
- 最后得到路径，让两条路径长度相等，再比较判断相交节点
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(); } };
四、二叉搜索树转换双向链表
思路：
- 设置head记录最左节点，设置prev记录上个访问的节点
- 中序遍历递归，首次初始化head和prev，后面利用prev和root进行双向链接
class Solution { public: TreeNode* head = nullptr; TreeNode* prev = nullptr; TreeNode* Convert(TreeNode* root) { if(root == nullptr) return nullptr; Convert(root->left); if(prev == nullptr) { head = root; prev = root; } else { prev->right = root; root->left = prev; prev = root; } Convert(root->right); return head; } };
五、构造二叉树
5.1 前序与中序
思路：
- 写子函数_buildTree，方便控制条件递归，参数新增prei，inbegin，inend
- 前序确定根，创建根节点，中序找到分割点rooti，递归分割左右子树子区间（先左后右）
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 rooti = inbegin; while(rooti <= inend && inorder[rooti] != preorder[prei]) { ++rooti; } ++prei; //分割左右子树子区间 root->left = _buildTree(preorder, inorder, prei, inbegin, rooti-1); root->right = _buildTree(preorder, inorder, prei, 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); } };
5.2 中序与后序
思路：
- 写子函数_buildTree，方便控制条件递归，参数新增posti，inbegin，inend
- 后序确定根，创建根节点，中序找到分割点rooti，递归分割左右子树子区间（先右后左）
class Solution { public: TreeNode* _buildTree(vector<int>& postorder, vector<int>& inorder, int& posti, int inbegin, int inend) { if(inbegin > inend) { return nullptr; } //后序确定根 TreeNode* root = new TreeNode(postorder[posti]); //查找中序分割点 int rooti = 0; while(rooti <= inend && inorder[rooti] != postorder[posti]) { ++rooti; } --posti; //分割左右子树子区间 root->right = _buildTree(postorder, inorder, posti, rooti+1, inend); root->left = _buildTree(postorder, inorder, posti, inbegin, rooti-1); return root; } TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) { int i = postorder.size()-1; return _buildTree(postorder, inorder, i, 0, inorder.size()-1); } };
六、二叉树的前中后序遍历（非递归）
6.1 前序
class Solution { public: vector<int> preorderTraversal(TreeNode* root) { stack<TreeNode*> st; vector<int> v; //v.reserve(100); TreeNode* cur = root; while(cur || !st.empty()) { //访问一棵树 //1、左路节点 while(cur) { v.push_back(cur->val); st.push(cur); cur = cur->left; } //2、左路节点的右子树 TreeNode* top = st.top(); st.pop(); cur = top->right; } return v; } };
6.2 中序
class Solution { public: vector<int> inorderTraversal(TreeNode* root) { stack<TreeNode*> st; vector<int> v; //v.reserve(100); TreeNode* cur = root; while(cur || !st.empty()) { //1、左路节点 while(cur) { st.push(cur); cur = cur->left; } //2、左路节点的右子树 TreeNode* top = st.top(); st.pop(); v.push_back(top->val); cur = top->right; } return v; } };
6.3 后序
思路：
- 前中后序共同思路：先访问左路节点，再访问左路节点的右子树
- 利用stack记录左路节点，直到cur走到空
- 后序的关键：设置prev指针，记录上一个访问的节点
- 如果右为空 或者 右为prev，根节点出栈遍历，否则cur指向右
class Solution { public: vector<int> postorderTraversal(TreeNode* root) { stack<TreeNode*> st; vector<int> v; //v.reserve(100); TreeNode* prev = nullptr;//关键：设置前置指针 TreeNode* cur = root; while(cur || !st.empty()) { //1、左路节点 while(cur) { st.push(cur); cur = cur->left; } //2、左路节点的右子树 TreeNode* top = st.top(); //如果右为空，或者右为上一个访问的节点 if(top->right == nullptr || top->right == prev) { v.push_back(top->val); st.pop(); prev = top; } else { cur = top->right; } } return v; } };
真诚点赞，手有余香
