您好,登录后才能下订单哦!
这篇文章给大家介绍python二叉树问题的示例分析,内容非常详细,感兴趣的小伙伴们可以参考借鉴,希望对大家能有所帮助。
LeetCode 199. 二叉树的右视图[1]
给定一棵二叉树,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。
示例1
输入:[1,2,3,null,5,null,4]输出:[1,3,4]解释: 1 <--- / \2 3 <--- \ \ 5 4 <---
dfs 的思路就是直接递归求解左右子树各自能看到的右视图是什么,然后判断两个视图长度。
如果右子树右视图长度大于等于左子树右视图长度,那左子树完全被挡住。不用管左子树了,直接返回根结点加上右子树右视图就行了。
否则的话,左子树中超出右子树深度的部分不会被挡住,也会被看到,所以得拼接在右子树右视图后面。
bfs 的思路就是层次遍历了。对二叉树的每一层,只取最后一个结点就行了。
bfs 的话就得用一个队列来维护结点值了,那么怎么知道哪些结点是同一层的呢?最初的想法是用一个 pair
再保存一个深度值,但是这样有点多余了。
我们只需要每次队列中只保存同一层的结点,然后记录下队列大小。然后依次出队,直到出队个数达到之前记录的大小。并且同时将所有的下一层结点入队。这样就能保证这一层的结点全部出队之后,队列中只剩下了下一层的结点。
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; }};
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; }};
关于python二叉树问题的示例分析就分享到这里了,希望以上内容可以对大家有一定的帮助,可以学到更多知识。如果觉得文章不错,可以把它分享出去让更多的人看到。
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。