翻轉(zhuǎn)二叉樹，感覺做二叉樹的問題好像都是那一套公式，除了個(gè)別的問題解決不了，用上篇博客leetcode刷題之樹（二）的模型基本可以解決。總體來說就是樹基本都可以利用遞歸和迭代的方法去解決，在涉及到樹的遍歷的時(shí)候偏向于利用棧來存儲(chǔ)數(shù)據(jù)，在求和樹的層次相關(guān)的問題時(shí)偏向于利用隊(duì)列來存儲(chǔ)數(shù)據(jù)。 個(gè)人感覺迭代更好理解，因?yàn)檫f歸涉及回溯

?

class Solution { public:TreeNode* invertTree(TreeNode* root) {queue<TreeNode*>s;s.push(root);if(root==NULL)return root;while(!s.empty()){ TreeNode*h=s.front();TreeNode* temp=NULL;temp=h->left;h->left=h->right;h->right=temp;s.pop();if(h->left!=NULL)s.push(h->left);if(h->right!=NULL)s.push(h->right); }return root;} };

遞歸解決代碼較少，理解起來不如用隊(duì)列。

class Solution { public:TreeNode* invertTree(TreeNode* root) {if(root==NULL)return root;TreeNode* temp;temp=root->left;root->left=invertTree(root->right);root->right=invertTree(temp);return root;} };

?

這道題我按照官方思路，寫成c++的形式，應(yīng)該是哈希表定義的不對(duì)，老提示我有錯(cuò)誤，說stl庫(kù)里沒有insert這個(gè)函數(shù)，以后再解決。?

class Solution { public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {queue<TreeNode*> s;unordered_map<TreeNode*,TreeNode*> parent;parent.insert(root,NULL);s.push(root);while(!parent.find(p) ||!parent.find(q)){TreeNode* node=s.top();s.pop();if(node->left!=NULL){parent.insert(node->left,node);s.push(node->left);}if(node->right!=NULL){parent.insert(node->right,node);s.push(node->right);}}set<TreeNode*>ancestors;while (p!=NULL){ancestors.insert(p);p=parent.find(p);}while(!ancestors.find(q))q=parent.find(q);return q; } };

?

這個(gè)題比較抽象想到了就很好解決，屬于樹得動(dòng)態(tài)規(guī)劃問題。?

class Solution { public:pair<int, int> dfs(TreeNode *root) {if (root == nullptr) {return { 0, 0 };}auto left_pair = dfs(root->left);auto right_pair = dfs(root->right);return { root->val + left_pair.second + right_pair.second, max(left_pair.first, left_pair.second) + max(right_pair.first, right_pair.second) };}int rob(TreeNode* root) {auto p = dfs(root);return max(p.first, p.second);} }; //（1）當(dāng)前結(jié)點(diǎn)選擇偷+左右孩子不偷能拿出的錢 //（2）當(dāng)前結(jié)點(diǎn)不偷即求左右孩子最多能偷到的錢

?

與50位技術(shù)專家面對(duì)面20年技術(shù)見證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的leetcode刷题之树（三）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。