【每日算法Day 108】一道简单的二叉树题目,写法还是挺多的。

题目链接

LeetCode 199. 二叉树的右视图

题目描述

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

示例1

输入:
[1,2,3,null,5,null,4]
输出:
[1,3,4]
解释:
   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

题解

dfs

dfs 的思路就是直接递归求解左右子树各自能看到的右视图是什么,然后判断两个视图长度。

如果右子树右视图长度大于等于左子树右视图长度,那左子树完全被挡住。不用管左子树了,直接返回根结点加上右子树右视图就行了。

否则的话,左子树中超出右子树深度的部分不会被挡住,也会被看到,所以得拼接在右子树右视图后面。

bfs

bfs 的思路就是层次遍历了。对二叉树的每一层,只取最后一个结点就行了。

bfs 的话就得用一个队列来维护结点值了,那么怎么知道哪些结点是同一层的呢?最初的想法是用一个 pair 再保存一个深度值,但是这样有点多余了。

我们只需要每次队列中只保存同一层的结点,然后记录下队列大小。然后依次出队,直到出队个数达到之前记录的大小。并且同时将所有的下一层结点入队。这样就能保证这一层的结点全部出队之后,队列中只剩下了下一层的结点。

代码

dfs(c++)

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        if (!root) return {};
        vector<int> left = rightSideView(root->left);
        vector<int> right = rightSideView(root->right);
        vector<int> res = {root->val};
        for (auto x : right) res.push_back(x);
        for (int i = right.size(), sz = left.size(); i < sz; ++i) {
            res.push_back(left[i]);
        }
        return res;
    }
};

bfs(c++)

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> res;
        queue<TreeNode*> Q;
        if (root) Q.push(root);
        while (!Q.empty()) {
            int sz = Q.size();
            while (sz--) {
                TreeNode* node = Q.front();
                Q.pop();
                if (!sz) res.push_back(node->val);
                if (node->left) Q.push(node->left);
                if (node->right) Q.push(node->right);
            }
        }
        return res;
    }
};

关注公众号【算法码上来】,每日算法干货马上就来!


   转载规则


《【每日算法Day 108】一道简单的二叉树题目,写法还是挺多的。》 韦阳 采用 知识共享署名 4.0 国际许可协议 进行许可。
 上一篇
【每日算法Day 109】五大解法,带你深入了解完全背包方案数 【每日算法Day 109】五大解法,带你深入了解完全背包方案数
今天这题是完全背包问题 + 背包问题方案数,我一共列举了 5 种解法,层层递进优化。并且从两个角度殊途同归,最终优化到同一个式子。强烈建议掌握,对理解背包问题有很大帮助。 题目链接LeetCode 面试题 08.11. 硬币 题目描述给
2020-04-23
下一篇 
【每日算法Day 107】面试必考:良心推荐,一题三解,不看后悔一辈子 【每日算法Day 107】面试必考:良心推荐,一题三解,不看后悔一辈子
可能有些同学只会写 python ,看不懂 c++。但是一个是因为我懒,多解时不想再写一遍 python 了,一个是理解算法最重要,语言不重要。今天学妹发来一张图,我觉得说的很好。 题目链接LeetCode 1248. 统计「优美子数
2020-04-21
  目录