23.C++进阶：二叉树OJ|二叉树创建字符串|最近公共祖先|搜索树与双向链表|前中序构建二叉树|二叉树的非递归遍历
606. 根据二叉树创建字符串 - 力扣（LeetCode）
class Solution { public: string tree2str(TreeNode* root) { if (root == nullptr) return ""; string ret = to_string(root->val); if (root->left || root->right) { ret += '('; ret += tree2str(root->left); ret += ')'; } if (root->right) { ret += '('; ret += tree2str(root->right); ret += ')'; } return ret; } };236. 二叉树的最近公共祖先 - 力扣（LeetCode）
若是二叉搜索树
class Solution { public: bool IsInTree(TreeNode* root, TreeNode* x) { if(root == nullptr) return false; return root == x || IsInTree(root->left, x) || IsInTree(root->right, x); } TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if(root == NULL) return NULL; if(root == p || root == q) { return root; } bool pInLeft, pInRight, qInLeft, qInRight; pInLeft = IsInTree(root->left, p); pInRight =!pInLeft; qInLeft = IsInTree(root->left, q); qInRight =!qInLeft; if((pInLeft && qInRight) || (qInLeft && pInRight)) { return root; } else if(pInLeft && qInLeft) { return lowestCommonAncestor(root->left, p, q); } else if(pInRight && qInRight) { return lowestCommonAncestor(root->right, p, q); } assert(false); return NULL; } };class Solution { public: bool GetPath(TreeNode* root, TreeNode* x, stack<TreeNode*>& 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) { stack<TreeNode*> 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(); } };二叉搜索树与双向链表_牛客题霸_牛客网
class Solution { public: void InOrderConvert(TreeNode* cur, TreeNode*& prev) { if(cur == nullptr) return; InOrderConvert(cur->left, prev); // cur中序 // 当前节点的左，指向前一个节点 cur->left = prev; // 前一个节点的右，指向当前节点 if (prev) prev->right = cur; prev = cur; InOrderConvert(cur->right, prev); } TreeNode* Convert(TreeNode* pRootOfTree) { TreeNode* prev = nullptr; InOrderConvert(pRootOfTree, prev); TreeNode* head = pRootOfTree; while (head && head->left) { head = head->left; } return head; } };105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）
class Solution { public: TreeNode* _buildTree(vector<int>& preorder, vector<int>& 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 (inorder[rooti] == root->val) break; else rooti++; } //[inbegin,rooti-1],rooti,[rooti+1, inend] root->left = _buildTree(preorder, inorder, prei, inbegin, rooti-1); root->right = _buildTree(preorder, inorder, prei, rooti+1, inend); return root; } TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { int i = 0; TreeNode* root = _buildTree(preorder, inorder, i, 0, inorder.size()-1); return root; } };144. 二叉树的前序遍历 - 力扣（LeetCode）
class Solution { public: vector<int> preorderTraversal(TreeNode* root) { stack<TreeNode*> s; vector<int> v; TreeNode* cur = root; while(cur || !s.empty()) { //1、访问左路节点，左路节点入栈 while (cur) { v.push_back(cur->val); s.push(cur); cur = cur->left; } //2、依次访问左路节点的右子树 TreeNode* top = s.top(); s.pop(); //访问左路节点的右子树 --子问题 cur = top->right; } return v; } };94. 二叉树的中序遍历 - 力扣（LeetCode）
class Solution { public: vector<int> inorderTraversal(TreeNode* root) { stack<TreeNode*> s; vector<int> v; TreeNode* cur = root; while(cur || !s.empty()) { //1、访问左路节点，左路节点入栈 while (cur) { s.push(cur); cur = cur->left; } //2、依次访问左路节点的右子树 TreeNode* top = s.top(); s.pop(); // 栈里取到一个节点时，表示它的左子树访问完毕 v.push_back(top->val); //访问左路节点的右子树 --子问题 cur = top->right; } return v; } };145. 二叉树的后序遍历 - 力扣（LeetCode）
class Solution { public: vector<int> postorderTraversal(TreeNode* root) { stack<TreeNode*> s; vector<int> v; TreeNode* cur = root; TreeNode* prev = nullptr; while(cur || !s.empty()) { //1、访问左路节点，左路节点入栈 while (cur) { s.push(cur); cur = cur->left; } //2、依次访问左路节点的右子树 TreeNode* top = s.top(); // 栈里面top，代表top的左子树已经访问完了 //1. 当前节点的右子树为空，则访问当前节点 //右子树不为空，上一个访问的节点是右子树的根，代表右子树访问过了 //2. 右子树不为空，子问题访问右子树 if (top->right == nullptr || top->right == prev) { v.push_back(top->val); s.pop(); prev = top; } else { //访问左路节点的右子树 --子问题 cur = top->right; } } return v; } };