从C语言到C++_25(树的十道OJ题)力扣:606+102+107+236+426+105+106+144+94+145（上）：https://developer.aliyun.com/article/1521948
解析代码：（法一）
class Solution { public: bool Find(TreeNode* sub,TreeNode* x) { if(sub == nullptr) { return false; } return sub == x || Find(sub->left,x) || Find(sub->right,x); } TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if(root == p || root == q) // 只要其中一个是自己自己，自己就是公共祖先 { return root; } bool pInLeft,pInRight,qInLeft,qInRight; pInLeft = Find(root->left,p); pInRight = !pInLeft; // 依题意,p不在左边就在右边 qInLeft = Find(root->left,q); 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（H*N）H是树的高度，N是树的结点数，怎么优化到O(N)?
解析代码：（法二）
我们把要找的结点的所有祖先都用栈存起来，
（按前序找，不确定是不是就入栈，确定不是就pop掉继续找）
然后转化为链表相交问题：
class Solution { public: bool FindPath(TreeNode* root,TreeNode* x,stack<TreeNode*>& path) { if(root == nullptr) return false; path.push(root); // 不管是不是，先入栈 if(root == x) return true; // 找到返回true if(FindPath(root->left,x,path)) return true; // 左树找到返回true if(FindPath(root->right,x,path)) return true; // 右树找到返回true path.pop(); // 都找不到 return false; } TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { stack<TreeNode*> pPath,qPath; FindPath(root,p,pPath); FindPath(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(); // 相等，返回其中一个 } };
剑指 Offer 36. 二叉搜索树与双向链表 - 力扣（LeetCode）
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
为了让您更好地理解问题，以下面的二叉搜索树为例：
我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。
下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。
特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。
注意：本题与主站 426 题相同：力扣
注意：此题对比原题有改动。
（牛客一道差不多的题的链接：）
二叉搜索树与双向链表_牛客题霸_牛客网 (nowcoder.com)
解析代码：（牛客）
/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/ class Solution { public: void InOrderConvert(TreeNode* cur, TreeNode*& prev) // 希望就有一个prev,传引用 { if(cur == nullptr) { return; } InOrderConvert(cur->left,prev); cur->left = prev; // 走到中序这,知道cur的left和prev的right 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; } };
解析代码：（力扣）
力扣的就是在牛客的基础上改成双向链表：（要判空了）
/* // 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 treeToDoublyListInOrder(Node* cur,Node*& prev) { if(cur == nullptr) { return; } treeToDoublyListInOrder(cur->left,prev); cur->left = prev; // 走到中序这,知道cur的left和prev的right if(prev) { prev->right = cur; } prev = cur; // 往后走 treeToDoublyListInOrder(cur->right,prev); } Node* treeToDoublyList(Node* root) { if(root == nullptr) { return nullptr; } Node* prev = nullptr; treeToDoublyListInOrder(root,prev); Node* head = root; while(head && head->left) // 找链表的头结点 { head = head->left; } Node* tail = root; // 变成双向循环链表 while(tail && tail->right) { tail = tail->right; } head->left = tail; tail->right = head; return head; } };
105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）
难度中等
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
示例 1:
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]
示例 2:
输入: preorder = [-1], inorder = [-1]
输出: [-1]
提示:
1 <= preorder.length <= 3000inorder.length == preorder.length-3000 <= preorder[i], inorder[i] <= 3000preorder和inorder均 无重复 元素inorder均出现在preorderpreorder保证 为二叉树的前序遍历序列inorder保证 为二叉树的中序遍历序列
/** * 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* buildTree(vector<int>& preorder, vector<int>& inorder) { } };
解析代码：
class Solution { public: TreeNode* _buildTree(vector<int>& preorder, vector<int>& inorder, int& prei, int left, int right) { if (left > right) { return nullptr; } TreeNode* root = new TreeNode(preorder[prei++]); // 先构建好根 int ini = left; // 分割中序 while (ini <= right) { if (inorder[ini] == root->val) { break; } else { ini++; } } // [left,ini-1] ini [ini+1,right] 构建好根之后,构建根的左右子树 root->left = _buildTree(preorder, inorder, prei, left, ini - 1); root->right = _buildTree(preorder, inorder, prei, ini + 1, right); return root; } TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { int i = 0; return _buildTree(preorder, inorder, i, 0, inorder.size() - 1); } };
106. 从中序与后序遍历序列构造二叉树 - 力扣（LeetCode）
难度中等
给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
示例 1:
输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]
示例 2:
输入：inorder = [-1], postorder = [-1]
输出：[-1]
提示:
1 <= inorder.length <= 3000postorder.length == inorder.length-3000 <= inorder[i], postorder[i] <= 3000inorder和postorder都由 不同 的值组成postorder中每一个值都在inorder中inorder保证是树的中序遍历postorder保证是树的后序遍历
/** * 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* buildTree(vector<int>& inorder, vector<int>& postorder) { } };
解析代码：
class Solution { public: TreeNode* _buildTree(vector<int>& inorder, vector<int>& postorder, int& prei, int left, int right) { if (left > right) { return nullptr; } TreeNode* root = new TreeNode(postorder[prei--]); // 从后面开始new int ini = left; // 分割中序 while (ini <= right) { if (inorder[ini] == root->val) { break; } else { ini++; } } // [left,ini-1] ini [ini+1,right] 先构建右再构建左 root->right = _buildTree(inorder, postorder, prei, ini + 1, right); root->left = _buildTree(inorder, postorder, prei, left, ini - 1); return root; } TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) { int i = inorder.size() - 1; return _buildTree(inorder, postorder, i, 0, inorder.size() - 1); } };
从C语言到C++_25(树的十道OJ题)力扣:606+102+107+236+426+105+106+144+94+145（下）：https://developer.aliyun.com/article/1521948?spm=a2c6h.13148508.setting.19.50c04f0eHmAr4x
