学习算法的第一步就是树形联系题目。这几乎是所有问题的根基。这里将一些树形题目进行了分享，内容主要包括 －树的遍历 －求树的高度 －求树的最近公共祖先 －打印树的某个路径 废话不说了，现在就上代码：
/************************************************************************* > File Name: path.cpp > Author: Yuji CAO > Mail: yujicao@amazon.com > Created Time: 2016年08月13日 星期六 09时05分37秒 > 没有写过的已经会的程序，就是不会写 ************************************************************************/ #include<iostream> #include<vector> #include<unordered_map> #include<unordered_set> #include<sstream> #include<list> #include<queue> #include<stack> #include<string> #include<utility> #include<algorithm> using namespace std; struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int val):val(val),left(nullptr),right(nullptr){} }; namespace tree { /* 1 |\ 2 3 | |\ 4 5 6 1,2,3,4,#,5,6,#,#,#,#,#,# */ static TreeNode* buildTree(const string& dataInput) { //split vector<int> dataVec; int pre = -1; string data = dataInput; data += ","; for (int i = 0; i < data.size(); ++i) { if (data[i] == ',') { string s = data.substr(pre + 1, i - 1 - pre); pre = i; int a = numeric_limits<int>::min(); if (s != "#") { a = atoi(s.c_str()); } dataVec.push_back(a); } } if (dataVec.empty()) { return nullptr; } TreeNode* root = new TreeNode(dataVec[0]); queue<TreeNode*> q; q.push(root); int i = 1; while (i < dataVec.size()) { queue<TreeNode*> qq; while (!q.empty()) { TreeNode* cur = q.front(); q.pop(); int a = dataVec[i++]; if (a == numeric_limits<int>::min()) { cur->left = nullptr; } else { cur->left = new TreeNode(a); qq.push(cur->left); } a = dataVec[i++]; if (a == numeric_limits<int>::min()) { cur->right = nullptr; } else { cur->right = new TreeNode(a); qq.push(cur->right); } } q = qq; } return root; } class PrintPath { public: /* 1 |\ 2 3 | |\ 4 5 6 1,2,(4) 1,(2) 1,3,5 1,3,(5) 1,3,6 1,3,(6) 1,(3) (1) */ vector<int> print(int node, const TreeNode* const root) { stack<const TreeNode*> s; const TreeNode* cur = root; const TreeNode* pre = nullptr; while (!s.empty() || cur != nullptr) { while(cur != nullptr) { s.push(cur); if (cur->val == node) { return mkresult(s); } cur = cur->left; } if (!s.empty()) { const TreeNode* t = s.top(); if (pre == t->right || nullptr == t->right) { pre = t; s.pop(); cur = nullptr; } else { cur = t->right; } } } vector<int> ans; return ans; } private: vector<int> mkresult(stack<const TreeNode*>& s) { vector<int> ans; stack<const TreeNode*> rs; while (!s.empty()) { rs.push(s.top()); s.pop(); } while(!rs.empty()) { ans.push_back(rs.top()->val); rs.pop(); } return ans; } }; class ClosestParent { public: int get(int f, int s, const TreeNode* const root) { bool hasF = false; bool hasS = false; auto ans = getInner(f, s, root, hasF, hasS); return ans->val; } private: const TreeNode* getInner(int f, int s, const TreeNode* const root, bool& hasF, bool& hasS) { if (root == nullptr) { return nullptr; } if (root->val == f) { hasF = true; } if (root->val == s) { hasS = true; } bool hasF1 = false; bool hasS1 = false; const TreeNode* l = getInner(f, s, root->left, hasF1, hasS1); if (hasF1) hasF = true; if (hasS1) hasS = true; if (hasF1 && hasS1) { return l; } bool hasF2 = false; bool hasS2 = false; const TreeNode* r = getInner(f, s, root->right, hasF2, hasS2); if (hasF2) hasF = true; if (hasS2) hasS = true; if (hasF2 && hasS2) { return r; } if (hasF && hasS) return root; return nullptr; } }; class Height { public: /* 1 * |\ * 2 3 * | |\ * 4 5 6 * * 1,1->[1,1],[2,2],{[4,3]}; nullptr,3 * nullptr,3->[1,1],{[2,2]}; nullptr,2 * nullptr,2->{[1,1]}; 3,1 * 3,1->[3,2],{[5,3]}; nullptr,3 * nullptr,1->{[3,2]}; 6,2 * nullptr,1->{[6,3]}; nullptr,3 */ int get1(const TreeNode* const root) { stack<pair<const TreeNode*, int> > s; const TreeNode* cur = root; int ans = 0; int height = 0; while (!s.empty() || cur != nullptr) { while(cur != nullptr) { height += 1; s.push({cur, height}); cur = cur->left; } if (!s.empty()) { pair<const TreeNode*, int> t = s.top(); s.pop(); cur = t.first->right; height = t.second; } ans = max(height, ans) ; } return ans; } int get2(const TreeNode* const root) { if (root == nullptr) { return 0; } return 1 + max(get2(root->left), get2(root->right)); } }; class Visit { public: vector<int> postOrder(const TreeNode* const root, int i = 1) { vector<int> ans; if (i == 1) cout<<"1->",postOrder1(root, ans); else cout<<"2->",postOrder2(root, ans); return ans; } vector<int> inOrder(const TreeNode* const root, int i = 1) { vector<int> ans; if (i == 1) cout<<"1->",inOrder1(root, ans); else cout<<"2->",inOrder2(root, ans); return ans; } vector<vector<string> > level(const TreeNode* const root) { vector<vector<string> > ans; level1(root, ans); return ans; } private: void level1(const TreeNode* const root, vector<vector<string> >& ans) { queue<const TreeNode*> q; q.push(root); vector<string> ansEle; stringstream ss; ss<<root->val; ansEle.push_back(ss.str()); ans.push_back(ansEle); while (!q.empty()) { int i = q.size(); vector<string> ansEle; while (i > 0) { const TreeNode* t = q.front(); q.pop(); if (t->left) { stringstream ss; ss<<t->left->val; ansEle.push_back(ss.str()); q.push(t->left); } else { ansEle.push_back("#"); } if (t->right) { stringstream ss; ss<<t->right->val; ansEle.push_back(ss.str()); q.push(t->right); } else { ansEle.push_back("#"); } i -= 1; } ans.push_back(ansEle); } } void level2(const TreeNode* const root, vector<vector<int> >& ans) { queue<const TreeNode*> q; q.push(root); while (!q.empty()) { int i = q.size(); vector<int> ansEle; while (i > 0) { const TreeNode* t = q.front(); ansEle.push_back(t->val); q.pop(); if (t->left) { q.push(t->left); } if (t->right) { q.push(t->right); } i -= 1; } ans.push_back(ansEle); } } void inOrder1(const TreeNode* const root, vector<int>& ans) { if (root == nullptr) { return; } inOrder1(root->left, ans); ans.push_back(root->val); inOrder1(root->right, ans); } void inOrder2(const TreeNode* const root, vector<int>& ans) { stack<const TreeNode*> s; const TreeNode* cur = root; while (!s.empty() || cur != nullptr) { while(cur != nullptr) { s.push(cur); cur = cur->left; } if (!s.empty()) { const TreeNode* t = s.top(); ans.push_back(t->val); s.pop(); cur = t->right; } } } void postOrder1(const TreeNode* const root, vector<int>& ans) { if (root == nullptr) { return; } postOrder1(root->left, ans); postOrder1(root->right, ans); ans.push_back(root->val); } void postOrder2(const TreeNode* const root, vector<int>& ans) { stack<const TreeNode*> s; const TreeNode* cur = root; const TreeNode* pre = nullptr; while (!s.empty() || cur != nullptr) { while (cur != nullptr) { s.push(cur); cur = cur->left; } if (!s.empty()) { const TreeNode* t = s.top(); if (t->right == nullptr || t->right == pre) { pre = t; ans.push_back(t->val); s.pop(); cur = nullptr; } else { cur = t->right; } } } } }; }; int main() { TreeNode* root = tree::buildTree("1,2,3,4,#,5,6,#,#,#,#,#,#"); tree::Visit visit; auto ans = visit.postOrder(root, 2); for (auto ele : ans) { cout<<ele<<","; } cout<<endl; auto ans1 = visit.inOrder(root, 2); for (auto ele : ans1) { cout<<ele<<","; } cout<<endl; auto ans2 = visit.level(root); for (auto ele : ans2) { cout<<"["; for (auto eleInner : ele) { cout<<eleInner<<","; } cout<<"]"<<endl; } tree::Height height; auto ans3 = height.get1(root); cout<<"Height:\t"<<ans3<<endl; auto ans4 = height.get2(root); cout<<"Height:\t"<<ans4<<endl; tree::ClosestParent cp; cout<<"3,6->"<<cp.get(3, 6 , root)<<endl; cout<<"2,6->"<<cp.get(2, 6 , root)<<endl; tree::PrintPath pp; auto ans5 = pp.print(5, root); for (auto ele : ans5) { cout<<ele<<","; } cout<<endl; return 0; }