BM41. [输出二叉树的右视图]
https://www.nowcoder.com/exam/oj?tab=%E7%AE%97%E6%B3%95%E7%AF%87&topicId=295
BM41. 输出二叉树的右视图
题目的主要信息：
- 利用二叉树中序遍历结果及先序遍历结果构建一棵二叉树
- 打印二叉树的右视图，即二叉树每层最右边的结点元素
- 节点值互不相同
可以发现解这道题，我们有两个步骤：
- 建树
- 打印右视图
首先建树方面，先序遍历是根左右的顺序，中序遍历是左根右的顺序，因为节点值互不相同，我们可以根据在先序遍历中找到根节点（每个子树部分第一个就是），再在中序遍历中找到对应的值，从其左右分割开，左边就是该树的左子树，右边就是该树的右子树，于是将问题划分为了子问题。
打印右视图即找到二叉树每层最右边的结点元素，我们可以采取dfs或者bfs两种方式遍历树，根据记录的深度找到最右值。
方法一：递归建树+深度优先搜索
具体做法：
建树函数根据上述说的划分，可以使用递归解决，利用l1 r1 l2 r2分别记录子树部分在数组中分别对应的下标，并跟随函数进行递归。
dfs部分，采用两个栈，一个栈记录深度优先搜索结点的次序，一个栈记录与前者相应的深度，另利用一个哈希表来记录每层的最右的结点，因为结点值不重复，因此哈希表很适应。因为dfs是先序遍历的，根左右的顺序，因此同一层中后访问的必然是更右边的结点，因此按照顺序每次更新哈希表即可。
class Solution {
public:
//建树函数
//四个int参数分别是先序最左结点下标，先序最右结点下标
//中序最左结点下标，中序最右结点坐标
TreeNode* buildTree(vector<int>& xianxu, int l1, int r1, vector<int>& zhongxu, int l2, int r2)
{
if(l1 > r1 || l2 > r2)
return NULL;
TreeNode* root = new TreeNode(xianxu[l1]); //构建节点
int rootIndex = 0; //用来保存根节点在中序遍历列表的下标
//寻找根节点
for(int i = l2; i <= r2; i++)
{
if(zhongxu[i] == xianxu[l1])
{
rootIndex = i;
break;
}
}
int leftsize = rootIndex - l2; //左子树大小
int rightsize = r2 - rootIndex; //右子树大小
//递归构建左子树和右子树
root->left = buildTree(xianxu, l1 + 1, l1 + leftsize, zhongxu, l2 , l2 + leftsize - 1);
root->right = buildTree(xianxu, r1 - rightsize + 1, r1, zhongxu, rootIndex + 1, r2);
return root;
}
//深度优先搜索函数
vector<int> rightSideView(TreeNode* root) {
unordered_map<int, int> mp;//右边最深处的值
int max_depth = -1; //记录最大深度
stack<TreeNode*> nodes; //维护深度访问结点
stack<int> depths; //维护深度时的深度
nodes.push(root);
depths.push(0);
while (!nodes.empty()){
TreeNode* node = nodes.top();
nodes.pop();
int depth = depths.top();
depths.pop();
if (node != NULL) {
// 维护二叉树的最大深度
max_depth = max(max_depth, depth);
// 如果不存在对应深度的节点我们才插入
if (mp.find(depth) == mp.end())
mp[depth] = node->val;
nodes.push(node->left);
nodes.push(node->right);
depths.push(depth + 1);
depths.push(depth + 1);
}
}
vector<int> res;
for (int i = 0; i <= max_depth; i++)
res.push_back(mp[i]);
return res;
}
vector<int> solve(vector<int>& xianxu, vector<int>& zhongxu) {
vector<int> res;
if(xianxu.size() == 0) //空结点
return res;
//建树
TreeNode* root = buildTree(xianxu, 0, xianxu.size() - 1, zhongxu, 0, zhongxu.size() - 1);
//找每一层最右边的结点
return rightSideView(root);
}
};
复杂度分析：
- 时间复杂度：
，建树部分递归位
，中序遍历中寻找根节点最坏
- 空间复杂度：
方法二：哈希表优化的递归建树+层次遍历
具体做法：
对于方法一中每次要寻找中序遍历中的根节点很浪费时间，我们可以利用一个哈希表直接将中序遍历的元素与下标做一个映射，后续查找中序根结点便可以直接访问了。
同时除了深度优先搜索可以找最右结点，我们也可以利用层次遍历，借助队列，找到每一层的最右。值得注意的是：每进入一层，队列中的元素个数就是该层的结点数。因为在上一层他们的父节点将它们加入队列中的，父节点访问完之后，刚好就是这一层的所有结点。因此我们可以用一个size变量，每次进入一层的时候记录当前队列大小，等到size为0时，便到了最右边，记录下该结点元素。
class Solution {
public:
unordered_map<int, int> index;
//建树函数
//四个int参数分别是先序最左结点下标，先序最右结点下标
//中序最左结点下标，中序最右结点坐标
TreeNode* buildTree(vector<int>& xianxu, int l1, int r1, vector<int>& zhongxu, int l2, int r2)
{
if(l1 > r1 || l2 > r2)
return NULL;
int xianxu_root = l1;// 前序遍历中的第一个节点就是根节点
int zhongxu_root = index[xianxu[xianxu_root]];// 在中序遍历中定位根节点
TreeNode* root = new TreeNode(xianxu[xianxu_root]);
int leftsize = zhongxu_root - l2;// 得到左子树中的节点数目
root->left = buildTree(xianxu, l1 + 1, l1 + leftsize, zhongxu, l2, zhongxu_root - 1);
root->right = buildTree(xianxu, l1 + leftsize + 1, r1, zhongxu, zhongxu_root + 1, r2);
return root;
}
//深度优先搜索函数
vector<int> rightSideView(TreeNode* root) {
vector<int> res;
queue<TreeNode*> q;
q.push(root);
while(!q.empty())
{
int size = q.size(); //队列中的大小即是这一层的结点树
while(size--)
{
TreeNode* temp = q.front();
q.pop();
if(temp->left)
q.push(temp->left);
if(temp->right)
q.push(temp->right);
if(size == 0) //最右元素
res.push_back(temp->val);
}
}
return res;
}
vector<int> solve(vector<int>& xianxu, vector<int>& zhongxu) {
vector<int> res;
if(xianxu.size() == 0) //空结点
return res;
for (int i = 0; i < xianxu.size(); i++) {
index[zhongxu[i]] = i;
}
//建树
TreeNode* root = buildTree(xianxu, 0, xianxu.size() - 1, zhongxu, 0, zhongxu.size() - 1);
//找每一层最右边的结点
return rightSideView(root);
}
};
复杂度分析：
- 时间复杂度：
- 空间复杂度：
