1. 二叉树创建字符串
相信大部分人看了题目描述之后，都会和我一样一脸的懵逼。直到我看到了一个描述才恍然大悟
分为3种情况：
- 左右都为空 --省略
- 右为空，左不为空 – 省略
- 左为空，右不为空–不省略
这里复习一下二叉树的前序遍历、中序遍历、和后序遍历
前序的结果是：ABDEGCF
中序的结果是：DBGEACF
后序的结果是：DGEBFCA
class Solution { public: string tree2str(TreeNode* root) { if (root == nullptr) { return ""; } string 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; } };
2. 二叉树的层序遍历
思路大致是这样的：
一个队列，接着一个levelSize来记录每层有几个数据，如果这个数字是0，则表示这层的数据出完
出3将9和20带到队列，levelSize为2 。如此循环下去。
如果这个队列不为空，就一直循环下去，直到这个队列为空为止。
代码实现：
class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { queue<TreeNode*> q; int levelSize = 0; if (root) { q.push(root); levelSize = 1; } vector<vector<int>> vv; while (!q.empty()) // 如果队列不为空，就继续 { // 通过levelSize控制一层一层的出 vector<int> 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); // 更新下一层的个数 levelSize = q.size(); } return vv; } };
3. 二叉树的层序遍历Ⅱ
这个题目与上一题目，差不多，我们只需要将最后的答案逆置即可
4. 二叉树的最近公共祖先
思路一：公共祖先的特征，如果一个在左子树，一个在右子树。那么这个节点就是公共祖先。
class Solution { public: bool isInTree(TreeNode* root, TreeNode* x) { if (root == nullptr) { return false; } return x == root || isInTree(root->left, x) || isInTree(root->right, x); } TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if (root == nullptr) { return nullptr; } if (p == root || q == root) { return root; } // 判断p节点是在root的左边还是右边 bool pInLeft = isInTree(root->left, p); bool pInRight = !pInLeft; // 判断q节点是在root的左边还是右边 bool qInLeft = isInTree(root->left, q); bool qInRight = !qInLeft; if ((pInLeft && qInRight) || (pInRight && qInLeft)) { return root; } // 如果都在左边，则转换为在左树寻找公共祖先 else if (pInLeft && qInLeft) { return lowestCommonAncestor(root->left, p, q); } else { return lowestCommonAncestor(root->right, p, q); } } };
思路二：公共祖先的特征，如果一个在我的左子树，一个在我的右子树，我就是公共祖先
如果是搜索二叉树可以优化到O(N)
- 一个比根小，一个比根大，根就是公共祖先
- 都比根小，递归左树查找
- 都比根大，递归右树查找
但是这个题目我们并不是搜索二叉树，要求优化到O(N)
这里只能使用另外一种思路，将p和q的路径求出来，放到容器当中，转换为路径相交问题
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(); } };
上述代码的关键在于找到每个节点的路径
5. 二叉搜索树与双向链表
看到这个题目我们的第一个想法可能是把所有的节点拿出来，然后尾插到一个双向链表上，其实并没有这么简单，我们能够想到的出题人当然也能够想到。
这个题目有以下几个要求：
我们需要在原树上进行操作。
class Solution { public: void inorderTraversal(TreeNode* cur, TreeNode*& prev) { if (cur == nullptr) { return; } inorderTraversal(cur->left, prev); cur->left = prev; if (prev) { prev->right = cur; } prev = cur; inorderTraversal(cur->right, prev); } TreeNode* Convert(TreeNode* pRootOfTree) { TreeNode* prev = nullptr; inorderTraversal(pRootOfTree, prev); TreeNode* head = pRootOfTree; while (head && head->left) { head = head->left; } return head; } };
以上的这幅图是精髓所在
6. 从前序与中序遍历序列构造二叉树
class Solution { public: TreeNode* _buildTree(vector<int>& preorder, vector<int>& inorder, int& previ, int inbegin, int inend) { if (inbegin > inend) { return nullptr; } TreeNode* root = new TreeNode(preorder[previ]); // 分割出左右区间 int rooti = inbegin; while (rooti <= inend) { if (inorder[rooti] == preorder[previ]) { break; } else { rooti++; } } ++previ; // [inbegin, rooti - 1], rooti, [rooti + 1, inend] root->left = _buildTree(preorder, inorder, previ, inbegin, rooti - 1); root->right = _buildTree(preorder, inorder, previ, rooti + 1, inend); return root; } TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { int i = 0; return _buildTree(preorder, inorder, i, 0, inorder.size() - 1); } };
7. 二叉树的前序遍历(非递归)
class Solution { public: vector<int> preorderTraversal(TreeNode* root) { stack<TreeNode*> st; TreeNode* cur = root; vector<int> v; while (cur || !st.empty()) { // 1. 开始访问一棵树 // 2. 左路节点 // 3. 左路节点的右子树 while (cur) { v.push_back(cur->val); st.push(cur); cur = cur->left; } // 访问右子树 TreeNode* top = st.top(); st.pop(); // 子问题访问右子树 cur = top->right;// 这个地方非常重要 } return v; } };
8. 二叉树的中序遍历(非递归)
class Solution { public: vector<int> inorderTraversal(TreeNode* root) { stack<TreeNode*> st; TreeNode* cur = root; vector<int> v; while (cur || !st.empty()) { while (cur) { st.push(cur); cur = cur->left; } // 栈里面取到左路节点，左路节点的左子树访问完了 TreeNode* top = st.top(); st.pop(); v.push_back(top->val); cur = top->right; } return v; } };
8. 二叉树的后序遍历(非递归)
class Solution { public: vector<int> postorderTraversal(TreeNode* root) { stack<TreeNode*> st; TreeNode* cur = root; vector<int> v; TreeNode* prve = nullptr; while (cur || !st.empty()) { while (cur) { st.push(cur); cur = cur->left; } // 栈里面取到左路节点，左路节点的左子树访问完了 TreeNode* top = st.top(); // 右为空或者右已经访问过了，可以访问根节点 if (top->right == nullptr || top->right == prve) { v.push_back(top->val); st.pop(); prve = top; } else { cur = top->right; } } return v; } };
这里对非递归的三种代码进行对比：
