题目出处：606. 根据二叉树创建字符串 - 力扣（LeetCode）
class Solution {
public:
string tree2str(TreeNode* root)
{
if (root == nullptr)
return "";
string str = to_string(root->val); //将int类型的val转换成string类型
if (root->left || root->right) //左边或右边不为空，保留左边空括号
{
str += '(';
str += tree2str(root->left);
str += ')';
}
if (root->right) //右边为空时，不需要打印空括号
{
str += '(';
str += tree2str(root->right);
str += ')';
}
return str;
}
};?题目出处：102. 二叉树的层序遍历 - 力扣（LeetCode）
层序遍历即逐层地，从左到右访问所有节点，有两种思路：
①用两个队列，一个队列控制层序遍历的节点，一个控制节点的层数
②通过一个levelSize变量控制队列出的数据数量，当变量出完后用队列的size更新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;
//通过levelSize控制一层一层出
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里去
vv.push_back(v);
//更新下一层的数据
levelSize = q.size();
}
return vv;
}
};题目出处：107. 二叉树的层序遍历 II - 力扣（LeetCode）
只需要将上面的层序遍历逆置一下即可?
class Solution {
public:
vector<vector<int>> levelOrderBottom(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;
//通过levelSize控制一层一层出
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里去
vv.push_back(v);
//更新下一层的数据
levelSize = q.size();
}
reverse(vv.begin(), vv.end());
return vv;
}
};题目出处：236. 二叉树的最近公共祖先 - 力扣（LeetCode）
方法一的大体思路是：如果给定的两个节点一个在右树一个在左树，那么这棵树的根节点就是我的公共祖先，所以我们先实现一个函数来判断给定的两个节点在树两边的位置，然后递归去走，如下代码：
class Solution
{
public:
bool IsIntree(TreeNode* root, TreeNode* x)
{
if (root == nullptr)
return false;
return root == x || 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) //p或q有一个是根，root就是最近公共节点
return root;
//判断pq在树的左边还是右边
bool pInLeft = IsIntree(root->left, p);
bool pInRight = !pInLeft;
bool qInLeft = IsIntree(root->left, q);
bool qInRight = !qInLeft;
if ((pInLeft && qInRight) || (qInLeft && pInRight)) //一个在根的左边一个在根的右边，那么根就是最近公共节点
return root;
else if (pInLeft && qInLeft) //都在左树，就递归到左子树去找公共祖先
return lowestCommonAncestor(root->left, p, q);
else //都在右树，就递归到右子树去找公共祖先
return lowestCommonAncestor(root->right, p, q);
}
};?这是一种思路，但是这种思路有很大缺点，因为必须要求是满二叉树或者完全二叉树的时候时间复杂度才是O(logN)，其他的都是O(N^2)，所以我们采用方法二会更好
方法二的大体思路和以前数据结构求链表相交节点的那个题目类似，用栈来解决问题，虽然需要申请一点空间，但是可以使时间复杂度搭配O(N)，属于典型的空间换时间，如下代码和注释：
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();
}
};题目出处：二叉搜索树与双向链表_牛客题霸_牛客网 (nowcoder.com)
给的树说二叉搜索树，所以我们以中序遍历来访问树实现排序，?只改变树节点的指向，left为链表的prev，right为链表的next，如下代码：
class Solution
{
public:
void InOrderConvert(TreeNode* cur, TreeNode*& prev) //直接通过中序遍历访问二叉树，
{
if (cur == nullptr)
return;
InOrderConvert(cur->left, prev);
//中序遍历时，使每个节点的left指向前驱节点prev
//让每个节点的right指向prev，将双向链表的节点搞清楚
cur->left = prev; //这里cur出现的顺序顺序就是中序
if (prev) //prev最开始是空，要判断一下
{
prev->right = cur;
}
prev = cur; //往后迭代走
InOrderConvert(cur->right, prev);
}
TreeNode* Convert(TreeNode* pRootOfTree)
{
TreeNode* prev = nullptr; //建立前驱节点方便链接
InOrderConvert(pRootOfTree, prev);
TreeNode* head = pRootOfTree;
while (head && head->left) //现在的pRootOfTree是树的根节点位置不是链表头结点位置，一直往前迭代即可
{
head = head->left;
}
return head;
}
};题目出处：105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）
从题目我么可以看出，前序的整数数组preorder和inorder可以确定根，中序可以分割处左右子树?
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)
{
if (inorder[rooti] == root->val)
{
break;//找到了
}
else
{
rooti++;
}
}
//分割后的区间为[inbegin,rooti-1] ini [rooti,inend]
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);
}
};