提到樹首先肯定是樹的三個遍歷即前中后 序遍歷。樹的遍歷可以通過兩種方式實現，一種是最常見的最簡單遞歸，一種是借用棧來進行迭代。雖然兩者實現的形式不一樣，但是兩者的思想是一樣的。都是有點類似于回溯算法的思想，拿中序遍歷來說，中序遍歷的順序是左根右，無論是棧還是遞歸我們都先遍歷到左子樹，當遍歷完最深層的左子樹之后，開始返回最近的父節點遍歷右子樹，只不過迭代利用了棧的后進先出的特性，對右子樹進行了保存。貼代碼

遞歸實現中序遍歷

class Solution { public:vector<int>res;vector<int> inorderTraversal(TreeNode* root) {if(root) {inorderTraversal(root->left);res.push_back(root->val);inorderTraversal(root->right);}return res;} };

迭代實現中序遍歷

class Solution { public:vector<int> inorderTraversal(TreeNode* root) {stack<TreeNode*>s;vector<int>res;while(root ||s.size()){while(root){s.push(root);root=root->left;}root=s.top();s.pop();res.push_back(root->val);root=root->right;}return res;} };

在刷二叉搜索樹的時候遇到求不同的二叉搜索樹的問題，此問題可以用動態規劃解決，也可以利用卡塔蘭樹解決。

其實我們應該叫明安圖數。更便于計算的公式定義如下：

遞推公式如下：

1.括號化問題。2.出棧次序問題。3.將多邊行劃分為三角形問題。

2012騰訊實習招聘筆試題
在圖書館一共6個人在排隊，3個還《面試寶典》一書，3個在借《面試寶典》一書，圖書館此時沒有了面試寶典了，確保三個人都能借到書，求他們排隊的總數？

阿里巴巴的筆試題目：說16個人按順序去買燒餅，其中8個人每人身上只有一張5塊錢，另外8個人每人身上只有一張10塊錢。燒餅5塊一個，開始時燒餅店老板身上沒有錢。16個顧客互相不通氣，每人只買一個。問這16個人共有多少種排列方法能避免找不開錢的情況出現。

?

?

?

?動態規劃題解方法根據上邊介紹的遞推公式寫出。

class Solution { public:int numTrees(int n) {vector<int> g(n+1);g[1]=1;g[0]=1;for(int i=2;i<=n;i++){for(int j=1;j<=i;j++)g[i]+=g[j-1]*g[i-j];}return g[n];} };

明安圖解決

class Solution { public:int numTrees(int n) {long c = 1;for(int i = 0; i < n; i++)c = c * 2 * (2 * i + 1) /(i + 2);return c;} };

知道了中序遍歷這道題就可以直接利用迭代的方法秒殺。

?

這道題是讓我們去驗證父節點是否大于左子結點（a），且小于右子結點(b)。我們肯定是需要遍歷這棵樹的，中序遍歷是先遍歷到最深層的左葉子結點，然后就去遍歷父節點，這個時候我們要 判斷a只需將正在遍歷的葉子結點用tmp保存，然后看是否大于等于父節點即可，大于就是返回錯誤，然后再返回去遍歷最近的右子結點，注意這個時候tmp保存的是父節點，所以還是判斷tmp是否大于等于右子節點（root->val）。就是tmp始終保存的是上一輪的值，然后拿著tmp和當前的root去比較。代碼如下：

/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/ class Solution { public:bool isValidBST(TreeNode* root) {long tmp=LONG_MIN;stack<TreeNode*>s;while(root ||s.size()!=0 ){while(root){s.push(root);root=root->left;}root=s.top();s.pop();if(tmp>=root->val)return false;tmp=root->val;root=root->right;}return true;} };

?

雖然標記的 這是一道簡單的題目，但是我一開始也沒有想出來，看是否對稱只需要看左子樹的左結點和右子樹的右結點是否相等，左子樹的右結點和右子樹的左結點是否相等。

遞歸代碼如下

class Solution { public:bool isSymmetric(TreeNode* root) {return helper(root,root);}bool helper(TreeNode* t1,TreeNode* t2){if(!t1 && !t2) return true;if(!t1 || !t2) return false;return (t1->val==t2->val)&& helper(t1->left,t2->right) && helper(t1->right,t2->left);} };

其實通過隊列或者棧去迭代思想是一樣的

class Solution { public:bool isSymmetric(TreeNode* root) {if(root==NULL) return true;stack<TreeNode*> s;s.push(root->left);s.push(root->right);while(s.size()){TreeNode* t1=s.top();s.pop();TreeNode* t2=s.top();s.pop();if(!t1 && !t2) continue;if(!t1 || !t2) return false;if(t1->val!=t2->val) return false;s.push(t1->left);s.push(t2->right);s.push(t1->right);s.push(t2->left);}return true;} };

?

?

?

?

總結

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

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。