【面试经典 150 | 二叉树层序遍历】二叉树的右视图

文章目录

写在前面
Tag
题目来源
解题思路
- 方法一：层序遍历
- 方法二：深度优先搜索
写在最后

写在前面

本专栏专注于分析与讲解【面试经典150】算法，两到三天更新一篇文章，欢迎催更……

专栏内容以分析题目为主，并附带一些对于本题涉及到的数据结构等内容进行回顾与总结，文章结构大致如下，部分内容会有增删：

Tag：介绍本题牵涉到的知识点、数据结构；
题目来源：贴上题目的链接，方便大家查找题目并完成练习；
题目解读：复述题目（确保自己真的理解题目意思），并强调一些题目重点信息；
解题思路：介绍一些解题思路，每种解题思路包括思路讲解、实现代码以及复杂度分析；
知识回忆：针对今天介绍的题目中的重点内容、数据结构进行回顾总结。

Tag

【二叉树】【层序遍历】【深搜】【广搜】

题目来源

199. 二叉树的右视图

解题思路

方法一：层序遍历

思路

使用层序遍历的方法，返回二叉树每一层的最后一个节点。

如果对于层序遍历知识不熟悉，可以参考广度优先搜索（1）之树的层序遍历和【二叉树的四种遍历——前序、中序、后续和层序遍历】。

算法

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
	vector<int> rightSideView(TreeNode* root) {
		vector<int> res;
		if (root == NULL)
			return res;

		queue<TreeNode*> q;
		q.push(root);

		while (!q.empty()) {
			int size = q.size();
            TreeNode *node = nullptr;
			while(size--)  {
				node = q.front();
				q.pop();
                if (node->left) q.push(node->left);
				if (node->right) q.push(node->right);
			}
            res.emplace_back(node->val);
		}
		return res;
	}
};

复杂度分析

时间复杂度： $O (n)$ ， $n$ 是二叉树中的节点数，每个节点最多入队出队各一次。

空间复杂度： $O (n)$ 。

方法二：深度优先搜索

思路

我们对树进行深度优先搜索，在搜索的过程中需要总是先访问右子树。那么对于每一层来说，我们在这层看到的第一个节点及就是一定是最右边的节点。

如何保证总是先访问右子树？利用栈的后进先出的特点，依次将当前节点的左、右节点压入栈中，那么栈中弹出的节点顺序就是先右再左子节点了。

如何实现 我们在这层看到的第一个节点及就是一定是最右边的节点 ？维护一个表示层深的局部变量，以此作为哈希表的键，二叉树当前层深所在层的最后节点值作为哈希表的值。

只有当前层深未曾出现在哈希表时，才更新哈希表，这样加上利用栈存放节点，便可以保证 “我们在这层看到的第一个节点及就是一定是最右边的节点”。

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        unordered_map<int, int> mostRNodeDepth2Val;
        int maxDepth = -1;

        stack<TreeNode*> nodeStk;   // 节点栈
        stack<int> depthStk;        // 与节点对应的深度栈
        nodeStk.push(root);
        depthStk.push(0);

        while (!nodeStk.empty()) {
            TreeNode* node = nodeStk.top(); nodeStk.pop();
            int depth = depthStk.top(); depthStk.pop();

            if (node != nullptr) {
                maxDepth = max(maxDepth, depth);

                // 不存在对应深度的节点，我们才插入
                if (mostRNodeDepth2Val.find(depth) == mostRNodeDepth2Val.end()) {
                    mostRNodeDepth2Val[depth] = node->val;
                }

                nodeStk.push(node->left);
                nodeStk.push(node->right);
                depthStk.push(depth + 1);
                depthStk.push(depth + 1);
            }
        }

        vector<int> rightView;
        for (int depth = 0; depth <= maxDepth; ++depth) {
            rightView.push_back(mostRNodeDepth2Val[depth]);
        }
        return rightView;
    }
};

复杂度分析

时间复杂度： $O (n)$ ，深搜最多访问每个节点一次。

空间复杂度： $O (n)$ ，最坏情况下，栈内包含接近树高度的节点数量，占用 $O (n)$ 空间。