根据二叉树创建字符串
本题的关键在于什么情况要省略括号，什么情况不能省略：
- 左右为空可以省略括号
- 左不为空，右为空可以省略括号
- 左为空,右不为空不能省略括号
class Solution {
public://1.左右为空可以省略括号//2.左不为空，右为空可以省略括号//3.左为空,右不为空不能省略括号string tree2str(TreeNode* root) {string ret;if (root == nullptr){return ret;}ret += to_string(root->val);if (root->left || root->right){ret += '(';ret += tree2str(root->left);ret += ')';}if (root->right){ret += '(';ret += tree2str(root->right);ret += ')';}return ret;}
};
二叉树的层序遍历
层序遍历咋一看很简单，借助队列就能实现，但是关键在于如何把每一层的结点区分开来，放到不同的vector中。这里采用的方法是使用一个计数器count来记录本层的结点数，count减到0时，本层结点已经遍历完了，此时队列中的就是下一层的结点，用队列的元素个数更新count即可。
class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> ret;if (root == nullptr){return ret;}queue<TreeNode*> q;q.push(root);int count = 1;//记录本层的结点数while (!q.empty()){vector<int> v;while (count--){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);}}ret.push_back(v);count = q.size();}return ret;}
};
二叉树的最近公共祖先
思路：找到根结点到p结点和q结点的路径，对比两个路径即可得到答案，时间复杂度O(n)
class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {vector<TreeNode*> pPath;vector<TreeNode*> qPath;findPath(root, p, pPath);findPath(root, q, qPath);int minSize = min(pPath.size(), qPath.size());int i = 0;for (; i < minSize; i++){if (pPath[i] != qPath[i]){break;}}return pPath[i - 1];}bool findPath(TreeNode* root, TreeNode* target, vector<TreeNode*>& path){if (root == nullptr){return false;}path.push_back(root);if (root == target){return true;}if (findPath(root->left, target, path)){return true;}if (findPath(root->right, target, path)){return true;}//回溯--恢复现场path.pop_back();return false;}
};二叉搜索树转双向链表
要将二叉搜索树转换为有序的双向链表，那么肯定与中序遍历有关。中序遍历过程中用prev记录上一个遍历的结点，cur记录当前结点，prev->right = cur, cur->left = prev即可。
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 = cur;InOrderConvert(cur->right, prev);}TreeNode* Convert(TreeNode* pcurOfTree) {TreeNode* ret = pcurOfTree;if (ret == nullptr){return ret;}//找到最小的结点--也就是重新链接后双链表的头结点while (ret->left){ret = ret->left;}TreeNode* prev = nullptr;InOrderConvert(pcurOfTree, prev);return ret;}
};
根据前序序列与中序序列构建二叉树
手工构建二叉树很容易，本题难点在于如何将手动构建的过程转化成代码。想一想手工构建的过程。如何确定二叉树的根结点？看前序序列。如何确定左右子树有哪些结点？看中序序列。如何构建左右子树呢？ 先确定根节点，这样又转化成了第一个问题。
牢记这一点：前序序列确定根结点。，中序序列确定左右子树有哪些结点。怎么表示左右子树的结点？用一个区间标识范围即可。
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]);prei++;//根据中序序列确定左右子树的结点int pos = inbegin;while (pos <= inend) {if (root->val == inorder[pos]){break;}pos++;}//[inbegin, pos - 1] [pos + 1, inend]root->left = _buildTree(preorder, inorder, prei, inbegin, pos - 1);root->right = _buildTree(preorder, inorder, prei, pos + 1, inend);return root;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {int prei = 0;return _buildTree(preorder, inorder, prei, 0, inorder.size()- 1);}
};根据后序序列和中序序列构建二叉树
思路和上一题类似，不过要注意postorder要从后往前遍历，并且要先构建右子树，再构建左子树。
class Solution {
public:TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {int posti = postorder.size() - 1;return _buildTree(inorder, postorder, posti, 0, inorder.size() - 1);}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]);posti--;//中序序列确定左右子树int pos = inbegin;while (pos <= inend){if (root->val == inorder[pos]){break;}pos++;}//[inbegin, pos - 1] [pos + 1, inend]//构建右子树和左子树root->right = _buildTree(inorder, postorder, posti, pos + 1, inend);root->left = _buildTree(inorder, postorder, posti, inbegin, pos - 1);return root;}
};二叉树的前序遍历迭代版本
递归写法很简单，如何用迭代来完成呢？
将一颗树分为左路结点和左路结点的右子树，遍历到一颗树的左路结点时就访问它，并将它放入栈中，继续访问下一个左路结点。当左路结点访问完后，从栈中取结点，该结点就是最近的一个左路结点，接下来访问它的右子树，又回到了最开始的步骤。
class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {stack<TreeNode*> st;vector<int> ret;TreeNode* cur = root;while (cur || !st.empty()){//遍历左路结点并访问while (cur){ret.push_back(cur->val);st.push(cur);cur = cur->left;}//遍历左路结点的右子树TreeNode* top = st.top();cur = top->right;st.pop();}return ret;}
};二叉树的中序遍历迭代版本
和上一题类似，一颗树看作左路结点和左路结点的右子树，和前序遍历不同的是，结点的访问时机不同。前序遍历是遍历到某个结点时就要访问它，而中序遍历，遍历到某个结点时先不访问，将它存入栈中，当再把它从栈中取出来时，代表它的左子树已经访问过了，接下来要访问右子树，此时就是访问该结点的时机。
class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {stack<TreeNode*> st;vector<int> ret;TreeNode* cur = root;while (cur || !st.empty()){//遍历左路结点while (cur){st.push(cur);cur = cur->left;}TreeNode* top = st.top();st.pop();//访问左路结点ret.push_back(top->val);//遍历左路结点的右子树cur = top->right;}return ret;}
};二叉树的后序遍历迭代版本
同样，一棵树分为左路结点和左路结点的右子树。左路结点的访问访问时机和前两道题又有所不同。遍历到左路结点时将它存入栈中，不能访问，当它的左子树遍历完时，从栈中取出，此时还是不能访问，要取遍历它的右子树，访问完右子树后，再次从栈中取出，此时才能访问并出栈。
本题难点在于，当你把结点从栈中取出来时，你如何知道它的右子树是否已经访问了呢？此时应该访问这个结点，还是暂时不访问，去遍历它的右子树呢？有两种方案：
1.设置flag值标记结点的右子树是否已经访问。
要让每一个结点都对应一个flag值，怎么做到呢？很简单，再建立一个栈，类型为bool，当结点入栈时，bool类型的变量也跟着入栈(注意不是同一个栈)，初始值为false。当从栈中取出结点时，也把对应的bool变量取出，如果为false，说明右子树还没有遍历，将bool变量置为true，访问右子树；若为true，说明右子树已经遍历，访问结点并出栈，同时将bool变量也出栈。结点入栈，bool变量入栈；结点出栈，bool变量也出栈，这样一来就能做到一一对应了。
lass Solution {
public:vector<int> postorderTraversal(TreeNode* root) {stack<TreeNode*> st;stack<bool> flag;vector<int> ret;TreeNode* cur = root;while (cur || !st.empty()){//遍历左路结点while (cur){st.push(cur);flag.push(false);cur = cur->left;}TreeNode* top = st.top();if (top->right == nullptr || flag.top() == true){//访问左路结点ret.push_back(top->val);st.pop();flag.pop();}else{//遍历左路结点的右子树flag.top() = true;cur = top->right;}}return ret;}
};2.标记前一个访问的结点
如果一个结点的右子树 (非空) 遍历完了，那么上一个访问的结点一定是该结点的右孩子。根据这一规律，只需创建一个prev变量来记录上一个访问的结点。如果一个结点从栈中取出来，若该结点右子树为空，则可以直接访问；若该结点右子树不为空且上一个访问的结点是该结点的右孩子，则也可以访问；否则就要先访问该结点的右子树。
class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {vector<int> ret;stack<TreeNode*> st;TreeNode* cur = root;TreeNode* prev = nullptr;while (cur || !st.empty()){//遍历左路结点while (cur){st.push(cur);cur = cur->left;}TreeNode* top = st.top();if (top->right == nullptr || top->right == prev){//访问左路结点ret.push_back(top->val);st.pop();prev = top;}else{//遍历右子树cur = top->right;}}return ret;}
};
