- I. 从上到下打印二叉树
- 2.从上到下打印二叉树 II
- 3.从上到下打印二叉树 III
- 4.二叉搜索树的后序遍历序列
题目链接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof/
这道题考察二叉树的层序遍历，也就是广度优先搜索(BFS),BFS通常借助队列先进先出的特点
基本步骤：
- 特例处理：树的根节点为空时，直接返回空列表
- 将根节点入队，打印结果列表ans
- BFS循环处理：当队列为空时结束循环
1.出队：搞一个指针(tmp)指向队首元素。队首元素出队
2.打印：将val添加至ans
3.添加子节点：若tmp指向的结点的左右子节点不为空，则将左右子节点入队
动图演示：
代码如下：
class Solution {
private:
vector ans;
queue q;
public:
vector levelOrder(TreeNode* root) {
if(!root)
return ans;
q.push(root);
while(q.size())
{
TreeNode* tmp = q.front();
ans.push_back(tmp->val);
q.pop();
if(tmp->left)
q.push(tmp->left);
if(tmp->right)
q.push(tmp->right);
}
return ans;
}
};
复杂度：
- 时间复杂度：O(N)
- 空间间复杂度：O(N)
题目链接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof/
和上面的题思路是一样的，不同的是本题需要一个vector来保存当前层的打印结果
当前层的循环条件：
- 循环次数为当前层节点数（即队列 queue 长度）
动图演示：
代码如下：
class Solution {
private:
queue q;
public:
vector> levelOrder(TreeNode* root) {
vector> ans;
if(!root) return ans;
q.push(root);
while(!q.empty())
{
vector v;
int size = q.size();
while(size)
{
TreeNode *tmp = q.front();
q.pop();
v.push_back(tmp->val);
if(tmp->left) q.push(tmp->left);
if(tmp->right) q.push(tmp->right);
size--;
}
ans.push_back(v);
}
return ans;
}
};
复杂度：
- 时间复杂度 O(N)
- 空间复杂度 O(N)
题目链接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/
和上面的题一样的，这题是偶数层反着打印
我们搞一个flag=1，每次循环*=-1，最后判断一下，当一层打印完后flag=-1就正常打印，flag=1先反转一下，再插入到最后的ans中。这题就不做动图了。
代码如下：
class Solution {
private:
queue q;
public:
vector> levelOrder(TreeNode* root) {
vector> ans;
if(!root) return ans;
q.push(root);
int falg = 1;
while(!q.empty())
{
falg *= -1;
vector v;
int size = q.size();
while(size)
{
TreeNode *tmp = q.front();
q.pop();
v.push_back(tmp->val);
if(tmp->left) q.push(tmp->left);
if(tmp->right) q.push(tmp->right);
size--;
}
if(falg == -1){
ans.push_back(v);
}
else
{
reverse(v.begin(),v.end());
ans.push_back(v);
}
}
return ans;
}
};
复杂度：
- 时间复杂度:O(N)
- 空间复杂度:O(N)
题目链接：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/
这题目和给定中序遍历和后序遍历创建二叉树的题目思路一样，我们看看它给定的数值能不能重建成二叉搜索树
二叉搜索树的性质，右结点比根节点大，左结点比根节点小，我们利用这个性质来接着道题
基本步骤：
-
递归结束：左区间大于等于右区间，说明此子树节点数量 ≤1 ，无需判别正确性，因此直接返回 true
-
划分左右子树：
遍历后序遍历的 [l.r]区间元素，寻找 第一个大于根节点 的节点，索引记为 k 。此时，可划分出左子树区间 [l,k-1] 右子树区间 [k, r - 1]根节点索引 root 。 -
判断是否为二叉搜索树：
1.左子树区间 内的所有节点都应
动图演示：
代码如下：
class Solution {
vector res;
public:
bool verifyPostorder(vector& postorder) {
res = postorder;
int n = postorder.size();
return dfs(0,n-1);
}
bool dfs(int l,int r)
{
if(l >= r) return true;
int root = res[r];//根节点
int k = l;
while(k < r && res[k] < root) k++;//找到左子树区间
for(int i = k; i < r;++i)
{
if(res[i] < root) //右子树中比根节点小，就返回false
return false;
}
return dfs(l,k-1) && dfs(k,r-1);//递归处理左右子树
}
};
复杂度：
- 时间复杂度 O(N^2) 每次调用 recur(i,j)recur(i,j) 减去一个根节点，因此递归占用 O(N)最差情况下（即当树退化为链表），每轮递归都需遍历树所有节点，占用 O(N) 。
- 空间复杂度 O(N) ： 最差情况下（即当树退化为链表），递归深度将达到 N 。
