二叉树的右视图 shuitang

199. 二叉树的右视图

给定一棵二叉树,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。

示例:

输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

解法

看到今天leetcode的每日一题,二叉树的右视图!我想起了一个月前字节二面时,面试官问的我这题……哎,当时也写出来了,不过因为后面项目提问部分发挥不好,挂在了二面……

算了,讲正事,这题的话,其实不难,思路也比较简单,就是一个二叉树的从右至左层次遍历(面试的时候,写的是从左至右,然后每次输出最后一个,可能麻烦些),然后每次输出第一个。我的写法如下:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> ans;
        if(root == nullptr) return ans;
        queue<pair<TreeNode*,int>> q;
        int cnt = 0;
        q.push(make_pair(root,1));
        
        while(!q.empty()){
            pair<TreeNode*,int> cur = q.front();
            q.pop();
            if(cur.first == nullptr) continue;
            if(cur.second > cnt){
                ans.push_back(cur.first->val);
                cnt++;
            }

            q.push(make_pair(cur.first->right,cur.second+1));
            q.push(make_pair(cur.first->left,cur.second+1));
        }
        return ans;

    }
};

然后,过了之后发现貌似内存消耗不小,然后去评论区逛了逛,发现可以这么写:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
	vector<int> res;
	if (!root) return res;
	queue<TreeNode*> q;
	q.push(root);
	while (!q.empty())
	{
		int size = q.size();
		res.push_back(q.front()->val);
		while (size--)
		{
			TreeNode* temp = q.front();
			q.pop();
			if (temp->right) q.push(temp->right);
			if (temp->left) q.push(temp->left);
		}
	}
	return res;
};

上面做法的内存消耗就小多了,不必每个节点都保存一个多余的层次信息,值得学习!