溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章給大家介紹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進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
