一.根据二叉树构建字符串题目链接:606. 根据二叉树创建字符串 - 力扣LeetCode/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: string tree2str(TreeNode* root) { string str; if(root nullptr) { return str; } str to_string(root-val); if(root-left || root-right) { str (; str tree2str(root-left); str ); } if(root-right) { str (; str tree2str(root-right); str ); } return str; } };二.二叉树的层序遍历题目链接:102. 二叉树的层序遍历 - 力扣LeetCode当前层出完了,后续(下一层节点都进入队列了)/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vectorvectorint levelOrder(TreeNode* root) { queueTreeNode* q; vectorvectorint vv; if(rootnullptr) { return vv; } int levelsize1; q.push(root); while(!q.empty()) { vectorint v; while(levelsize--) { TreeNode* front q.front(); q.pop(); v.push_back(front-val); if(front-left) { q.push(front-left); } if(front-right) { q.push(front-right); } } vv.push_back(v); levelsizeq.size(); } return vv; } };三.二叉树的层序遍历二题目链接:107. 二叉树的层序遍历 II - 力扣LeetCode和上一个题目是一样的,只要逆置一下就可以了/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vectorvectorint levelOrderBottom(TreeNode* root) { vectorvectorint ans; if(root nullptr) { return ans; } int x 1; queueTreeNode* q; q.push(root); while(q.size()) { vectorint v1; x q.size(); while(x--) { TreeNode* t1 q.front(); q.pop(); v1.push_back(t1-val); // cout t1-val ; if(t1-left) { q.push(t1-left); } if(t1-right) { q.push(t1-right); } } ans.push_back(v1); } reverse(ans.begin(),ans.end()); return ans; } };四.二叉树的最近公共祖先题目链接:236. 二叉树的最近公共祖先 - 力扣LeetCode/** * 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 IsIntree(TreeNode* t,TreeNode* x) { if(t nullptr) { return false; } return t x || IsIntree(t-left,x) || IsIntree(t-right,x); } TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if(root nullptr) { return nullptr; } if(root p || root q) { return root; } bool pInLeft IsIntree(root-left,p); bool pInRight !pInLeft; bool qInLeft IsIntree(root-left,q); bool qInRight !qInLeft; if((pInLeft qInRight) || (qInLeft pInRight)) { return root; } else if(pInLeft qInLeft) { return lowestCommonAncestor(root-left,p,q); } else { return lowestCommonAncestor(root-right,p,q); } } };这个代码效率是较慢的O(n ^ 2)我们来想一想,更加优秀的算法/** * 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 GetPath(TreeNode* root,TreeNode* x,stackTreeNode* path) { if(root nullptr) { return false; } path.push(root); if(root x) { return true; } if(GetPath(root-left,x,path)) { return true; } if(GetPath(root-right,x,path)) { return true; } path.pop(); return false; } TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { stackTreeNode* pPath,qPath; GetPath(root,p,pPath); GetPath(root,q,qPath); while(pPath.size() ! qPath.size()) { if(pPath.size() qPath.size()) { pPath.pop(); } else { qPath.pop(); } } while(pPath.top() ! qPath.top()) { pPath.pop(); qPath.pop(); } return pPath.top(); } };五.二叉树转化为排序的双向链表题目链接:LCR 155. 将二叉搜索树转化为排序的双向链表 - 力扣LeetCode/* // Definition for a Node. class Node { public: int val; Node* left; Node* right; Node() {} Node(int _val) { val _val; left NULL; right NULL; } Node(int _val, Node* _left, Node* _right) { val _val; left _left; right _right; } }; */ class Solution { public: void InOrderConvert(Node* cur,Node* prev) { if(cur nullptr) { return; } InOrderConvert(cur-left,prev); cur-left prev; if(prev) prev-right cur; prev cur; InOrderConvert(cur-right,prev); } Node* treeToDoublyList(Node* root) { if(root nullptr) { return nullptr; } Node* prev nullptr; InOrderConvert(root,prev); Node* head root; while(head head-left) { head head-left; } head-left prev; prev-right head; return head; } };六.前序和中序构建二叉树题目链接:105. 从前序与中序遍历序列构造二叉树 - 力扣LeetCode前序遍历,我们只能确定根(所以还要确定中序)/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: TreeNode* build(vectorint preorder,vectorint inorder,int prei,int inbegin,int inend) { if(inbegin inend) { return nullptr; } TreeNode* root new TreeNode(preorder[prei]); int rooti inbegin; while(rooti inend) { if(preorder[prei] inorder[rooti]) { break; } else { rooti; } } prei; root-left build(preorder,inorder,prei,inbegin,rooti - 1); root-right build(preorder,inorder,prei,rooti 1,inend); return root; } TreeNode* buildTree(vectorint preorder, vectorint inorder) { int i 0; return build(preorder,inorder,i,0,inorder.size()-1); } };七.二叉树的前序遍历题目链接:144. 二叉树的前序遍历 - 力扣LeetCode/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vectorint preorderTraversal(TreeNode* root) { stackTreeNode* st; TreeNode* cur root; vectorint v; while(cur || st.size()) { while(cur) { v.push_back(cur-val); st.push(cur); cur cur-left; } TreeNode* top st.top(); st.pop(); cur top-right; } return v; } };八.二叉树的中序遍历题目链接:94. 二叉树的中序遍历 - 力扣LeetCode这个只是访问的时机不太一样/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vectorint inorderTraversal(TreeNode* root) { stackTreeNode* st; TreeNode* cur root; vectorint v; while(cur || st.size()) { while(cur) { st.push(cur); cur cur-left; } TreeNode* top st.top(); st.pop(); v.push_back(top-val); cur top-right; } return v; } };九.二叉树的后序遍历题目链接:145. 二叉树的后序遍历 - 力扣LeetCode/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vectorint postorderTraversal(TreeNode* root) { stackTreeNode* st; TreeNode* cur root; TreeNode* prev nullptr; vectorint v; while(cur || st.size()) { while(cur) { st.push(cur); cur cur-left; } TreeNode* top st.top(); if(top-right nullptr || top-right prev) { v.push_back(top-val); st.pop(); prev top; } else { cur top-right; } } return v; } };