网创优客建站品牌官网
为成都网站建设公司企业提供高品质网站建设
热线:028-86922220
成都专业网站建设公司

定制建站费用3500元

符合中小企业对网站设计、功能常规化式的企业展示型网站建设

成都品牌网站建设

品牌网站建设费用6000元

本套餐主要针对企业品牌型网站、中高端设计、前端互动体验...

成都商城网站建设

商城网站建设费用8000元

商城网站建设因基本功能的需求不同费用上面也有很大的差别...

成都微信网站建设

手机微信网站建站3000元

手机微信网站开发、微信官网、微信商城网站...

建站知识

当前位置:首页 > 建站知识

python二叉树问题的示例分析

这篇文章给大家介绍python二叉树问题的示例分析,内容非常详细,感兴趣的小伙伴们可以参考借鉴,希望对大家能有所帮助。

创新互联公司10多年企业网站制作服务;为您提供网站建设,网站制作,网页设计及高端网站定制服务,企业网站制作及推广,对发电机维修等多个方面拥有多年的营销推广经验的网站建设公司。

题目链接

LeetCode 199. 二叉树的右视图[1]

 

题目描述

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

示例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 rightSideView(TreeNode* root) {        if (!root) return {};        vector left = rightSideView(root->left);        vector right = rightSideView(root->right);        vector 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 rightSideView(TreeNode* root) {        vector res;        queue 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;    }};

关于python二叉树问题的示例分析就分享到这里了,希望以上内容可以对大家有一定的帮助,可以学到更多知识。如果觉得文章不错,可以把它分享出去让更多的人看到。


网站题目:python二叉树问题的示例分析
文章地址:http://bjjierui.cn/article/gcccgg.html

其他资讯