- 一. 前序遍历类
- 1、二叉树的前序遍历（非递归）
- 2、根据二叉树创建字符串
- 二. 中序遍历类
- 1、二叉树的中序遍历（非递归）
- 三. 后序遍历类
- 1、二叉树的后序遍历（非递归）
- 四. 层序遍历类
- 1、二叉树的层序遍历
- 五. 搜索树类题目
- 1、二叉搜索树与双向链表
- 六. 其他类型题目
- 1、二叉树的最近公共祖先
1、二叉树的前序遍历（非递归）
题目连接
题目描述：
给你二叉树的根节点 root ，返回它节点值的前序遍历。
解题思路：
前序遍历的访问顺序是：根节点 -> 左子树 -> 右子树。
具体 *** 作方法：从根节点开始用一个栈存储根和它的左路节点，并依次把节点的val放入结果数组中。放完后我们取出栈顶元素，对于该节而言它本身和它的左路节点都已经访问过了，接下来循环回去访问它的右子树，重复这个过程完成整棵树的前序遍历。
完整代码：
class Solution {
public:
vector preorderTraversal(TreeNode* root)
{
vector ret;
stack st;
TreeNode* cur = root;
// 遍历以cur为根的树
while(cur || !st.empty())
{
// 1、先把根及其左路节点访问了并且放入栈中
while(cur)
{
ret.push_back(cur->val);
st.push(cur);
cur = cur->left;
}
// 2、拿出栈顶的节点，该节点及其它的左子树都已经被访问过
// 接下来只需访问它的右子树即可
cur = st.top()->right;
st.pop();
}
return ret;
}
};
性能分析：
- 时间复杂度：O(n)。每个节点都要入栈、出栈一次。
- 空间复杂度：O(n)。单支树时，所有节点同时都要入栈。
2、根据二叉树创建字符串
题目连接
题目描述：
你需要采用前序遍历的方式，将一个二叉树转换成一个由括号和整数组成的字符串。
空节点则用一对空括号 “()” 表示。而且你需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。
解题思路：
对照示例的输入输出来理解题目，按照前序遍历的顺序先处理根节点，如果存在左子树就处理左子树，然后右子树；如果不存在左子树但有右子树，在处理右子树之前要先加上一个空括号对来标志仅存在右子树。
可以使用 to_string 来把节点的val转化成字符串。
完整代码：
class Solution {
public:
string tree2str(TreeNode* root)
{
string s;
// 根节点为空的话返回空字符串
if(!root)
{
return s;
}
// 1、先处理根节点
s += to_string(root->val);
// 2、再处理左子树
if(root->left)
{
s += '(';
s += tree2str(root->left);
s += ')';
}
// 3、最后处理右子树
if(root->right)
{
// 注意：如果左子树为空的话，处理前要在前面加上一对空括号来标志后面的是右子树
if(root->left == nullptr)
{
s += "()";
}
s += '(';
s += tree2str(root->right);
s += ')';
}
// 4、返回最终结果
return s;
}
};
性能分析：
- 时间复杂度：O(n)。其中n是二叉树中的节点数目。
- 空间复杂度：O(n)。每个节点的处理都需要开辟一个栈帧。
1、二叉树的中序遍历（非递归）
题目描述：
给定一个二叉树的根节点 root ，返回它的中序遍历。
解题思路：
中序遍历顺序：左子树 -> 根节点 -> 右子树。
先把根节点及其它的左路节点都入栈，接下来取栈顶节点，该节点的特征是：左子树已经遍历完成，把该节点的val加入结果数组中，然后右子树重复上面的过程，最后中序遍历完整棵树。
完整代码：
class Solution {
public:
vector inorderTraversal(TreeNode* root)
{
vector ret;
stack st;
TreeNode* cur = root;
// cur是谁就遍历那棵树
while(cur || !st.empty())
{
// 1、先把根节点及其它的左路节点入栈
while(cur)
{
st.push(cur);
cur = cur->left;
}
// 2、拿出的栈顶节点左子树已经访问完成，接下来访问它自己及其它的右子树
TreeNode* top = st.top();
st.pop();
ret.push_back(top->val);
cur = top->right;
}
return ret;
}
};
性能分析：
- 时间复杂度：O(n)。每个节点都要入栈、出栈一次。
- 空间复杂度：O(n)。单支树时，所有节点同时都要入栈。
1、二叉树的后序遍历（非递归）
题目连接
题目描述：
给定一个二叉树，返回它的后序遍历。
解题思路：
先把根节点及其它的左路节点都入栈，接下来取栈顶节点，该节点的特征是：左子树已经遍历完成。这个节点能否加入结果数组取决于它的右子树是否遍历完成，如果没有的话，需要先遍历它的右子树。
完整代码：
class Solution {
public:
vector postorderTraversal(TreeNode* root)
{
vector ret;
stack st;
TreeNode* cur = root;
TreeNode* prev = nullptr;
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)
{
// 经过第一步的处理cur一定为空
// 所以这里面不用管cur
st.pop();
ret.push_back(top->val);
prev = top;
}
else
{
cur = top->right;
}
}
return ret;
}
};
性能分析：
- 时间复杂度：O(n)。每个节点都要入栈、出栈一次。
- 空间复杂度：O(n)。单叉树时，所以节点都要同时入栈。
1、二叉树的层序遍历
题目连接
题目描述：
给你一个二叉树，请你返回其按层序遍历得到的节点值。（即逐层地，从左到右访问所有节点）。
解题思路：
借助队列拿出每一层节点的同时按照从左到右的顺序存入下一层的所有节点，其核心代码下面这条，确保拿出当前层的节点：
for(size_t i = q.size(); i > 0; --i)
完整代码：
class Solution {
public:
vector> levelOrder(TreeNode* root)
{
// 1、如果根节点为空的话，返回一个空的二维数组
if(!root)
{
return vector>();
}
// 2、创建相关数据结构
queue q;
vector> vv;
// 3、借助队列搜索二叉树的每一层节点
q.push(root);
while(!q.empty())
{
vector v;
for(size_t i = q.size(); i > 0; --i)
{
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);
}
return vv;
}
};
性能分析：
- 时间复杂度：O(n)。需要遍历每一个节点。
- 空间复杂度：O(n)。队列的开销。总节点个数2^h - 1，最后一层节点个数为2^(h-1)，最后一层节点个数相当于总节点个数的一半，即n/2，所以空间复杂度渐进表示为O(n)。
1、二叉搜索树与双向链表
题目连接
题目描述：
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。如下图所示：
数据范围：输入二叉树的节点数 0 le n le 10000≤n≤1000，二叉树中每个节点的值 0le val le 10000≤val≤1000
要求：空间复杂度O(1)O(1)（即在原树上 *** 作），时间复杂度 O(n)O(n)
注意:
- 要求不能创建任何新的结点，只能调整树中结点指针的指向。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继
- 返回链表中的第一个节点的指针
- 函数返回的TreeNode，有左右指针，其实可以看成一个双向链表的数据结构
- 你不用输出双向链表，程序会根据你的返回值自动打印输出
输入描述：
二叉树的根节点
返回值描述：
双向链表的其中一个头节点。
示例1：
输入：
{10,6,14,4,8,12,16}
返回值：
From left to right are:4,6,8,10,12,14,16;From right to left are:16,14,12,10,8,6,4;
说明：
输入题面图中二叉树，输出的时候将双向链表的头节点返回即可。
示例2：
输入：
{5,4,#,3,#,2,#,1}
返回值：
From left to right are:1,2,3,4,5;From right to left are:5,4,3,2,1;
说明：
5
/
4
/
3
/
2
/
1
树的形状如上图 （单叉树，只有左分支）
解题思路：
题目要求将二叉搜索树转化成一个排序的双向链表，对于搜索树而言它的中序遍历是有序序列，我们考虑在中序遍历的过程中完成树到双向链表的转化。
传统的中序遍历过程中每次只能拿到一个节点。
想要转化成双向链表必须两两建立联系，考虑每次还能够传入当前节点的前一个节点prev，这样在每一次递归调用中：
- cur的左指针作为前驱指针，指向前一个节点prev。
- cur不知道它的下一个是谁，但是prev知道它的下一个是cur。
完整代码：
class Solution
{
private:
void InOrder(TreeNode* cur, TreeNode*& prev)
{
// 如果当前节点为空，不用处理
if(!cur)
{
return;
}
// 1、先处理左子树
InOrder(cur->left, prev);
// 2、处理上一个节点的后继和当前节点的前驱
// 此时当前节点的right还没处理，可以递归到右子树，到右子树中把当前节点作为prev完成后继的处理
if(prev)
{
prev->right = cur;
}
cur->left = prev;
prev = cur;
// 3、最后处理右子树
InOrder(cur->right, prev);
}
public:
TreeNode* Convert(TreeNode* pRootOfTree)
{
// 1、空树的话返回空指针回去就行
if(!pRootOfTree)
{
return nullptr;
}
// 2、在InOrder内完成双向链表的转化
TreeNode* prev = nullptr;
InOrder(pRootOfTree, prev);
// 3、通过传入的整棵树的根节点，往回找到双向链表的头结点
while(pRootOfTree->left)
{
pRootOfTree = pRootOfTree->left;
}
return pRootOfTree;
}
};
性能分析：
- 时间复杂度：O(n)。中序遍历了每一个节点。
- 空间复杂度：O(n)。每个节点都要开辟一个栈帧。
1、二叉树的最近公共祖先
题目连接
题目描述：
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
解题思路：
用两个栈分别记录两个节点的路径，接下来的思路可以转化为求相交链表的第一个相交节点。
-
求p、q两个节点所在的路径，把节点的地址存到各自的栈中
-
让长的那个栈先pop()距离步，使二者长度相等
-
两个栈一起pop()，找到第一个相同的节点就是最近公共祖先
完整代码：
class Solution
{
private:
// 记录节点的路径
bool FindPath(TreeNode* root, TreeNode* x, stack& s)
{
if(!root)
{
return false;
}
s.push(root);
if(root == x)
return true;
else if(FindPath(root->left, x, s) || FindPath(root->right, x, s))
return true;
else
s.pop();
return false;
}
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
{
stack pStack, qStack;
// 1、找到节点所在路径
FindPath(root, p, pStack);
FindPath(root, q, qStack);
// 2、长的那个路径先走距离步
stack* longStack = &pStack;
stack* shortStack = &qStack;
if(qStack.size() > pStack.size())
{
swap(longStack, shortStack);
}
while(longStack->size() > shortStack->size())
{
longStack->pop();
}
// 3、两个栈一起走，找到第一个相同的节点就是最近公共祖先
while(longStack->top() != shortStack->top())
{
longStack->pop();
shortStack->pop();
}
return longStack->top();
}
};
性能分析：
- 时间复杂度：O(n)。主要消耗在两次找找路径上。
- 空间复杂度：O(n)。查找路径时递归的栈帧消耗。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）