文章目录
- 力扣606. 根据二叉树创建字符串
- 力扣102. 二叉树的层序遍历
- 力扣236. 二叉树的最近公共祖先
- JZ36 二叉搜索树与双向链表
- 力扣105--通过前序和中序遍历构造二叉树
- 力扣144--二叉树的前序遍历(非递归)
- 力扣94--二叉树的中序遍历(非递归)
- 力扣145--二叉树的后序遍历(非递归)
力扣606. 根据二叉树创建字符串
题目链接:力扣606
class Solution {
public:void _tree2str(TreeNode* root, string& str){str += to_string(root->val);if(root->left){str += '(';_tree2str(root->left, str);str += ')';}if(root->left == nullptr && root->right){str += "(";str += ")";}if(root->right){str += '(';_tree2str(root->right, str);str += ')';}}string tree2str(TreeNode* root) {string str;_tree2str(root, str);return str;}
};
力扣102. 二叉树的层序遍历
力扣102
本质就是是一个广度优先搜索, — > 借助队列来完成。
class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {if(root == nullptr)return vector<vector<int>>();queue<TreeNode*> q;q.push(root);vector<vector<int>> vv;while(!q.empty()){int sz = q.size();vector<int> v;while(sz--){TreeNode* node = q.front();q.pop();v.push_back(node->val);if(node->left)q.push(node->left);if(node->right)q.push(node->right);}vv.push_back(v);}return vv;}
};
力扣236. 二叉树的最近公共祖先
力扣236
解题思路 : 我们用一个函数 bool inTree(BTreeNode* root, BTreeNode* x) 去判断这个目标节点p, q是在root的那一侧,
如果都是在左侧, 则到root的左侧去找, 如果都在右侧, 那就到root的右侧去找。
另外的话, p 或者q是root的话, 直接返回root就行
class Solution {
public:bool inTree(TreeNode* root, TreeNode* x){if (root == nullptr)return false;if (root->val == x->val)return true;return inTree(root->left, x) || inTree(root->right, x);}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q){if (root == p || root == q)return root;bool pLeft = inTree(root->left, p), pRight = !pLeft;bool qLeft = inTree(root->left, q), qRight = !qLeft;if (pLeft && qLeft){return lowestCommonAncestor(root->left, p, q);}else if (pRight && qRight){return lowestCommonAncestor(root->right, p, q);}else{return root;}return nullptr;}
};
JZ36 二叉搜索树与双向链表
题目链接: 牛客JZ36
class Solution {
public:void _Convert(TreeNode* root, TreeNode*& pre) //注意一下, 要传引用!!!!!{if(root == nullptr)return;_Convert(root->left, pre);root->left = pre;if(pre)pre->right = root;pre = root;_Convert(root->right, pre);}TreeNode* Convert(TreeNode* pRootOfTree) {if(pRootOfTree == nullptr)return nullptr;TreeNode* pre = nullptr;_Convert(pRootOfTree, pre);TreeNode* head = pRootOfTree; //这个根节点肯定是在中间的, 通过向前找即可。while(head->left) head = head->left;return head;}
};
力扣105–通过前序和中序遍历构造二叉树
力扣105
核心思路 : 通过前序遍历找到根节点, pi是前序遍历的下标,
然后通过中序遍历确定左右子树的范围
根的下标rooti 左树的区间范围 [inbegin rooti-1] 右树的区间范围 : [rooti+1, inend]。
class Solution {
public:TreeNode* _buildTree(vector<int>& preorder, vector<int>& inorder, int& pi, int inbegin, int inend){if(inend < inbegin) //区间不存在的情况{return nullptr; }TreeNode* root = new TreeNode(preorder[pi]);pi++; int rooti = inbegin; //找出根节点, 分出左,右子树。while(rooti <= inend){if(root->val != inorder[rooti])rooti++;elsebreak;}root->left = _buildTree(preorder, inorder, pi, inbegin, rooti-1);root->right = _buildTree(preorder, inorder, pi, rooti+1, inend);return root;} TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {int pi = 0; // 前序遍历的下标return _buildTree(preorder, inorder, pi, 0, inorder.size() - 1);}
};
力扣144–二叉树的前序遍历(非递归)
力扣144
class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {vector<int> v;TreeNode* cur = root;stack<TreeNode*> st;while(cur || !st.empty()){while(cur){st.push(cur);v.push_back(cur->val);cur = cur->left;}TreeNode* top = st.top();st.pop();cur= top->right;}return v;}
};
力扣94–二叉树的中序遍历(非递归)
力扣94
class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int>v;TreeNode* cur = root;stack<TreeNode*> st;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;}
};
力扣145–二叉树的后序遍历(非递归)
力扣145
和前序遍历基本上一样。
前序遍历是 : 根, 左, 右
后序遍历是 : 左,右, 根
核心 : 将后序看出 根, 右, 左 – >最后的结果逆置即可。
我们只用先将右路节点入栈并且访问, 然后出栈的时候将左树节点的右路节点入栈。
然后循环, 最后逆置数组即可。
class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {vector<int> v;TreeNode* cur = root;stack<TreeNode*> st;while(cur || !st.empty()){while(cur){st.push(cur);v.push_back(cur->val);cur = cur->right;}TreeNode* top = st.top();st.pop();cur = top->left;}reverse(v.begin(), v.end());return v;}
};